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

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23: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;