题目描述

Alice 得到了一个 $0 \sim n-1$ 的排列 $a$，并且得知了一个新的函数 $\text{mex}$。$\text{mex}(S)$ 的值为整数集合 $S$ 中未出现的最小自然数。

此时 Alice 突然变身成为 Angry Alice，她将对你发出 $q$ 次询问，每次询问给出 $l,r$，你需要立刻给出 $\text{mex}(\{ a_l,a_{l+1}, \cdots, a_r \})$ 的值。

输入格式

第一行两个正整数 $n,q$。

第二行共 $n$ 个数，保证为 $0 \sim n-1$ 的排列。

接下来 $q$ 行，每行两个正整数 $l,r$，表示一次询问。

输出格式

共 $q$ 行，每行一个整数，表示询问的答案。

4 2
3 0 1 2
2 3
1 4

2
4

数据范围

• 对于 $60\%$ 的数据：$n,q \leq 10^3$；

• 对于 $100\%$ 的数据：$n,q \leq 10^5$。

• 对于所有数据，$1 \leq n \leq 10^5, 1\leq q \leq 10^5, 1\leq l \leq r \leq n$。