题目描述

给定一个长度为 $n$ 的数列 $A$, 数列的第 $i$ 个元素是 $A_i$ (从 1 开始编号)。你需要回答 $q$ 个询问, 每个询问的参数是一个二元组 $(l, r)(l \leq r)$, 表示查询 $\operatorname{mex}\left(\left\{A_l, A_{l+1}, \cdots, A_r\right\}\right)$ 的值。

所谓 $m e x$, 就是 SG定理中那个函数, 也就是"Minimum Exclusive"的缩写。对一个非负整数组成的集合 $S$, $\operatorname{mex}(S)$ 的值等于最小的不属于集合 $S$ 的非负整数。

输入格式

输入文件第一行包含 2 个空格隔开的正整数 $n$ 和 $q$, 代表序列 $A$ 的长度和询问个数。 输入文件第二行包含 $n$ 个空格隔开的非负整数, 第 $i$ 个数表示 $A_i$ 的值。 接下来 $q$ 行, 每行包含 2 个空格隔开的正整数 $l$ 和 $r(1 \leq l \leq r \leq n)$, 表示一个查询的参数。

输出格式

输出文件应当包含 $q$ 行, 每行一个正整数, 表示输入文件中对应询问的答案。

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

3
0
3
2
4

样例解释

第1个询问: $\operatorname{mex}(\{0,2,1\})=3$.

第 2 个询问: $\operatorname{mex}(\{2,1\})=0$.

第3个询问: $\operatorname{mex}(\{0,2,1,0\})=3$.

第 4 个询问: $\operatorname{mex}(\{1,0,1,3\})=2$.

第5个询问: $\operatorname{mex}(\{2,1,0,1,3,2\})=4$.

数据规模与约定

对于 $10 \%$ 数据，满足 $n, q \leq 100$ 。

对于 $30 \%$ 数据，满足 $n, q \leq 10000$ 。

对于 $50 \%$ 数据，满足 $n, q \leq 50000$ 。

对于 $100 \%$ 数据，满足 $n, q \leq 200000 ; 0 \leq A_i \leq 200000 ; A_i$ 均为非负整数； $1 \leq l \leq r \leq$ $n ; l$ 和 $r$ 均为正整数；数据有一定梯度。

题目来源

By Xhr