找第k小的数

【题目描述】

看到很短的题目会让人心情愉悦，所以给出一个长度为N的序列A1,A2,A3,...,AN，

现在有M个询问，每个询问都是Ai...Aj中第k小的数等于多少。

【输入格式】

第一行两个正整数N，M。

第二行N个数，表示序列A1,A2,...,AN。

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

询问Ai...Aj中第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<=N<=10,000，1<=M<=10,000，A[i]<=100,000;

在100%的数据中，1<=N<=100,000,1<=M<=100,000,A[i]<=1,000,000;