2918. K-th Number

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly $k$-th order statistics in the array segment.

That is, given an array $a[1\dots n]$ of different integer numbers, your program must answer a series of questions $Q(i,j,k)$ in the form: “What would be the $k$-th number in $a[i\dots j]$ segment, if this segment was sorted?”
For example, consider the array $a=(1,5,2,6,3,7,4)$. Let the question be $Q(2,5,3)$. The segment $a[2\dots 5]$ is $(5,2,6,3)$. If we sort this segment, we get $(2,3,5,6)$, the third number is $5$, and therefore the answer to the question is $5$.