时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给出一个整数序列 \(A[1]..A[n]（0≤A[i]≤1000000）\)，需要你编写一个程序回答任意前 \(i\) 个整数中第 \(k\) 大的整数。

【输入格式】

　　第一行包含两个正整数 \(n,m\)，\(n\) 表示序列元素数目，\(m\) 表示查询数。
　　第二行为 \(A[1]..A[n]\)。
　　接下来的 \(m\) 行，每行一包含两个整数：\(i k\)，表示查询 \(A[1]..A[i]\) 中第 \(k\) 大的整数。

【输出格式】

　　针对每条指令，输出查询结果。针对第 2 种操作，如果没有满足条件的元素，输出None。

【输入输出样例】

　Input

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

　Output

3
8
3
6
4
5
1
4

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(1≤m≤500000\)。

【来源】

　　Mr.he