16 人解决，21 人已尝试。
25 份提交通过，共有 69 份提交。
4.9 EMB 奖励。
单点时限: 2.0 sec
内存限制: 256 MB
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 -th order statistics in the array segment.
That is, given an array of different integer numbers, your program must answer a series of questions in the form: “What would be the -th number in segment, if this segment was sorted?”
For example, consider the array . Let the question be . The segment is . If we sort this segment, we get , the third number is , and therefore the answer to the question is .
The first line of the input file contains — the size of the array, and — the number of questions to answer .
The second line contains different integer numbers not exceeding by their absolute values — the array for which the answers should be given.
The following lines contain question descriptions, each description consists of three numbers: Q(i, j, k)$.
For each question output the answer to it — the -th number in sorted segment.
7 3 1 5 2 6 3 7 4 2 5 3 4 4 1 1 7 3
5 6 3