Consider a data structure which keeps track of mode $($most frequent item$)$ of a dynamic

collection of keys. The keys are positive integers. They are not necessarily unique and can

have duplicates. We have three operations insert$(x),$ delete$(x)$ and findmode$().$ Show

that not both insert and findmode can be done in less than $o(logn)($Hint: use Element

Distinctness Problem$).$ Also, design a data structure which can perfrom all three operations

in $O(logn)$ in the worst case. Please give proper details of the structure and the functions.

For example, a sequence of operations insert $(8),$ insert $(9),$ insert $(10),$ insert $(10),$

insert $(8),$ insert $(7),$ insert$(8),$ findmode$()$ produces $8$ as the answer. Further, if we

apply delete$(8),$ delete$(8),$ findmode$()$ it will output $10$ as the answer.