Suppose we are interested in dynamically maintaining a set S of integers, which is initially empty, while supporting the following two operations:

add(v): Adds value v to set S.

median( ): Returns the current median value of the set. For a set with even cardinality, we define the median as the average of the two most central values.

We will store each element of the set in one of two priority queues: amin-oriented priority queue, Q⁺, of all elements greater than or equal to the current median value, and amax-oriented priority queue, Q⁻, of all elements less than the current median value.

a. Explain how to perform the operation median( ) in O(1) time given such a representation.

b. Explain how to performthe operation S.add(k) in O(logn) time, where n is the current cardinality of the set, while maintaining such a representation.