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

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 kth.in 输出文件 kth.out

题目描述

看到很短的题目会让人心情愉悦,所以给出一个长度为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<=10000,1<=M<=10000,A[i]<=100000;
在100%的数据中,1<=N<=100000,1<=M<=100000,A[i]<=1000000;