3649: 经典字符串问题(第五轮03)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：2
题目描述
给定一个 1 到 n 的排列，分别为a1, a2, … , an 。对于每个数， 都可以看成一个字 符串，那么 n 个串就可以根据字典序来排序。
比如字符串 “123”小于字符串“124”，而字符串“123”的字典序大于字符串“12”。
现在给出 q 个询问，每个询问的格式形如 l, r, k，对于每个询问都需要回答在区 间 [l, r] 中的第 k 小字典序是哪个数。
输入
第一行两个整数 n 和 q 表示排列的长度和询问的个数。 第二行 n 个数表示 a1, a2, … , an 。
接下来 q 行，每行三个整数 l, r, k 表示一个询问。
输出
对于每个询问，输出一行整数表示答案。如果不存在答案，输出-1。
样例输入 复制
5 1
1 5 3 4 2
1 3 2样例输出 复制
3提示
【数据范围】
对于20%的数据满足1 ≤ n, q ≤ 500
对于40%的数据满足1 ≤ n, q ≤ 5000
对于100%的数据满足1 ≤ n, q ≤ 1e5， 1 ≤ l ≤ r ≤ n， 1 ≤ k ≤ n。