2918. K-th Number

单点时限: 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

16 人解决,21 人已尝试。

25 份提交通过,共有 69 份提交。

4.9 EMB 奖励。

创建: 7 年,12 月前.

修改: 1 年,8 月前.

最后提交: 4 月,3 周前.

来源: Northeastern Europe 2004, Northern Subregion