A data structure for holding numbers in 2 sets, using BST? Design a data structure for holding numbers in two sets:

Init - initiate the DS with two empty sets. O(1)

Insert(a,S) - insert number a to set S (S could be X or Y). O(log(n)). (n is the total number of numbers in the DS)

Find - find a number a in the DS such that the number of numbers in X that are smaller than a equals the number of numbers in Y that are bigger than a, if exists such number. O(1)



My attempt is using 2 augmented balanced binary search trees, each one presents set X or Y, insert into it the new number and saving in each node information for finding what is the number of numbers in X that are smaller than this node and the number of numbers on Y that are bigger than that node. 

But given that information how could I implement the Find procedure in O(1)? Or maybe someone have better design (preferably using augmented BST)?
Since it's your exercise, I don't want to prevent you from finding the solution on your own, but I'll give you some possible hints:

Big hint:


   You can do some work during the Insert operation to make any subsequent Find run fast.


Think about that one for a while.



If you're still stuck, here are some more specific hints.  I recommend you think about each one for 15 minutes or more before moving on to the next one.

Hint #2:


   Suppose you wanted to implement an operation InsertAndFind(a,S), that effectively does Insert(a,S) followed by Find().  Could you make that run in O(log n) time?


Hint #3:


   It would also be possible to have a single data structure (e.g., a single augmented balanced binary search tree), with some information in each node.


Hint #4:


   What information would you want to keep in a node, to determine whether that node is something that could be returned in response to a future Find query?