Migrated from Lutece 2865 修复木琴

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

有这么一个木琴，它有 $n+2$ 个音条，从左到右按 $0$ 到 $n+1$ 编号。每个音条能发出的音高各不相同，并且都在 $[0,n+1]$ 范围内。

有一天不知道是谁觉得这些木质音条当柴烧不错，把一些音条取走了，只剩下了 $[l,r]$ 区间内的音条。

现在 Kanade 负责修理这个木琴。她会按音高从小到大的顺序重新安装被取走的音条，她已经放好了一个缺失的音条了，请问她下一个要放哪个音高的音条？

Input

第一行两个正整数 $n,q\ (1\le n,q\le 10^6)$，表示排列长度与询问次数。

接下来一行 $n$ 个整数 $p_1,p_2,\ldots, p_n\ (0\le p_i\le n-1)$，表示编号在 $1$ 到 $n$ 的音条的音高。

接下来 $q$ 行，每行两个正整数 $l,r\ (1\le l\le r\le n)$，表示一次询问。每次询问互相独立，也就是说，你可以认为 Kanade 不会真的把上一次询问回答的音条放在木琴上。

Output

对于每个询问，输出一行表示答案。

Samples

5 3
1 0 4 2 3
1 1
4 5
1 4

2
1
5

Resources

The 20th UESTC Programming Contest Preliminary