3315. 不是最大的,也是很大的

单点时限: 2.0 sec

内存限制: 256 MB

没有 Description 也是很大的!

输入格式

第一行两个整数 $n, q$ $(1\leq n, q\leq10^5)$。

第二行 $n$ 个整数,表示 $a_1, a_2, \ldots, a_n$ $(-10^9\leq a_i\leq10^9)$。

接下来 $q$ 行,每行三个整数 $l, r, k$ $(1\leq l\leq r\leq n, 1\leq k\leq r-l+1)$,分别表示区间左端点、右端点,第 $k$ 大。

输出格式

对于每次询问,输出一个整数,表示 $a_l, a_{l+1}, \ldots, a_r$ 中第 $k$ 大的数。

样例

Input
8 5
2 0 4 4 7 6 2 9
5 7 1
1 8 8
4 6 3
1 8 6
6 7 2
Output
7
0
4
2
2
Input
7 3
1 2 5 4 2 2 2
4 7 1
4 7 2
4 7 3
Output
4
2
2

9 人解决,15 人已尝试。

13 份提交通过,共有 96 份提交。

6.9 EMB 奖励。

创建: 3 年前.

修改: 2 年,10 月前.

最后提交: 5 月,1 周前.

来源: N/A