字符串问题

题目描述

给定一个$1$到$n$的排列，分别为$a_1,a_2,...,a_n$。对于每个数，都可以看成一个字符串，那么$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

数据范围

$20pts:$$n,q \leq 500$

$40pts:$$n,q\leq 5000$

$100pts:n ,q \leq 10^5$