题目描述

农夫$JC$的果园里有一排长度为 $n$ 的神奇果树，当摘下一颗果实的时候就会自动长出一颗果实，今日农夫$JC$准备采集 $m$ 个果子，但他已经厌烦了日常采摘，觉得一个个的采摘太无趣了，他想要这个过程变得 $interstring$ 一点，于是他决定每次在从左往右果实个数大于 $x$ 个的第 $k$ 棵果树上摘一颗果子，但他只想摘果子，不想数数，所以他现在想要知道每次该摘的那棵果树上有多少颗果子。

输入格式

第 $1$ 行为三个正整数 $n$ ，$m$ ，代表果树棵数和今日准备采集的果实数。

第 $2$ 行为 $n$ 个整数 $a_1 ... a_n$ ，代表从左往右每棵果树上的果实数。

接下来 $m$ 行

每行为两个正整数 $x$ 和 $k$ ，代表果实个数大于 $x$ 个和满足前面条件的第 $k$ 棵果树。

$( 1~\leq~n~\leq~10^5 )$ $(1~\leq~m~\leq~10^5 )$ $(1~\leq~a_i~\leq~10^9 )$ $(1~\leq~x~\leq~10^9 )$ $(1~\leq~k~\leq~10^6 )$

输出格式

输出共 $m$ 行

每行输出一个整数，代表该次该摘的那棵果树上有多少颗果子。

如果找不到从左往右果实个数大于 $x$ 个的第 $k$ 棵果树，则输出 $-1$ 。

样例

10 5 
13 11 4 9 7 3 2 6 8 1 
5 4 
9 2 
7 4 
13 1 
1 10

7 
11 
8 
-1 
-1

提示

样例解释：样例中果树分布是：${13,11,4,9,7,3,2,6,8,1}$

第一个查询让找果实个数大于 $5$ 的第 $4$ 棵果树，则为第 $5$ 棵果树，上面有 $7$ 个果实，所以输出 $7$ 。

​第四个查询让找果实个数大于 $13$ 的第 $1$ 棵果树，果园里没有果实个数大于 $13$ 的果树，所以输出 $-1$ 。

​第五个查询让找果实个数大于 $1$ 的第 $10$ 棵果树，果园里果实个数大于 $1$ 的果树只有 $9$ 棵，所以输出 $-1$ 。

by JC