930. [河南省队2012] 找第k小的数

【题目描述】

看到很短的题目会让人心情愉悦，所以给出一个长度为N的序列 $A_1, A_2, A_3, \dots, A_N$，

现在有M个询问，每个询问都是 $A_i \dots A_j$ 中第k小的数等于多少。

【输入格式】

第一行两个正整数 $N, M$。

第二行N个数，表示序列 $A_1, A_2, A_3, \dots, A_N$。

紧着的M行，每行三个正整数 $i, j, k(k \le j-i+1)$，表示

询问 $A_i \dots A_j$ 中第k小的数等于多少。

【输出格式】

共输出 $M$ 行，第 $i$ 行输出第 $i$ 个询问的答案。

【样例输入1】

4 3
4 1 2 3
1 3 1
2 4 3
1 4 4 

【样例输出1】

1
3
4

【样例输入2】

5 5
4 2 9 9 10
1 3 1
2 4 3
1 4 4
3 5 2
2 5 2

【样例输出2】

2
9
9
9
9

【提示】

询问区间的第 $k$ 小值并非严格第 $k$ 小，例如样例2中第4个询问，询问3到5中第2小的数，

答案输出9，并不是严格第2小的10。

在 $50$% 的数据中，$1 \le N \le 10,000, 1 \le M \le 10,000, A_i \le 100,000$;

在 $100$% 的数据中，$1 \le N \le 100,000, 1 \le M \le 100,000, A_i \le 1,000,000$;