I am using JAVA Thank you very much!

Hint: use two binary search tree

Once Frodo saves the world from Sauron and comes back to Shire, he takes an interest in mathematics. After learning about medians, he decides to forge a new median to rule them all. The lord of the medians (name it x) for an array A of numbers of length n is defined as follows: For each 0 kn 1, let Sh be the set of numbers {A [0j, . . . , Alk]). Also, let mk be the lower median of the set Sk. The lord of the medians for A will be m1 m2 m3 x. . . x mn-1. Gollum who is somehow still alive has asked you to help him find this precious number. Input Format The first line of the input is n, the size of the array. The next line consists of n distinct numbers Constraints 1