Problem Link: https://www.spoj.com/problems/MKTHNUM/

Solution Idea: (Merge Sort Tree)

• • At first, take input and store the input in a pair array where the first element of the i^th pair is the value a_i and the second element of the i^th pair is i.
  • Sort the pair array with ascending order of a_i
  • Build a merge sort tree using the second element of each pair of sorted pair array.
  • Now for each query i,j,k at first check how many numbers in range i to j inclusive are present in the left subtree of the current node in merge sort tree. Let the value is x. So if x<=k then it’s sure that the answer is in the left subtree. So we will go to the left subtree of the current node with k. Otherwise, we will go to right subtree of the current node with k-x;
  • In this manner when we reach a leaf node we can say that this node contains the index of our answer.