题目描述

有一个长度为 $n$ 的数组 $a_1,a_2,\ldots,a_n$。有 $m$ 次询问，每次询问一个区间内最小的没有出现过的自然数。

输入格式

第一行包含两个整数 $n,m$。

第二行包含 $n$ 个整数。

从第三行开始，每行包含两个整数 $l,r$，表示一次询问。

输出格式

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

样例

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

1
2
3
0
3

样例解释

如上所述。

数据范围与提示

• 对于 $30\%$ 的数据，$1 \le n,m \le 10^3$；
• 对于 $100\%$ 的数据，$1 \le n,m \le 2\times 10^5$，$0 \le a_i \le 10^9$，$1 \le l \le r \le n$。