This seems like a very good problem unfortunately my mind has been unable to make much progress. Therefore hints would be very appreciated :D. Here is the problem:

Today, we have a very interesting problem for you. Given an array A of N integers indexed from 1 to N, you need to perform following two types of queries :

• Change the value of A[x] to k.

• Find the kth ranked element in the subarray A[x..y] (x and y inclusive). An element is said to have kth rank if its position is k when the subarray is sorted in ascending order.

Can you perform these queries efficiently?