【题目描述】

给定一个长度为 $n$ 的整数序列，第 $i$ 个数记为 $a_i$。

接下来进行 $m$ 次询问。

第 $i$ 次询问给定一个区间 $[l_i,r_i]$，请输出这个区间内所有数的 MEX。

一个集合的 MEX 指没有在集合中出现过的最小非负整数。

【输入描述】

第一行输入两个整数 $n,m$，表示序列长度和询问次数。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，第 $i$ 行输入两个整数 $l_i,r_i$，表示一次询问的区间。

保证：

• $1\le n,m\le 3000$；
• $0\le a_i\le n$；
• $1\le l_i\le r_i\le n$。

【输出描述】

输出 $m$ 行，第 $i$ 行表示第 $i$ 次询问区间的 MEX。

【样例 1】

【样例 1 输入】

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

【样例 1 输出】

3
0
2

【样例 1 解释】

区间 $[1,3]$ 中出现了 $0,1,2$，MEX 为 $3$；

区间 $[2,4]$ 中没有 $0$，MEX 为 $0$。

【样例 2】

【样例 2 输入】

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

【样例 2 输出】

5
1
1
1