It is easy to prove that for a given range the best answer comes when we make the pillers height = element after sorting the range.
So the task is very simple. You have to find the middle element after sorting the elements. If you use merge sort tree it will find the middle element in . To process queries it will take .
We can reduce the complexity to by using Persistent Segment Tree.