题目描述

牛牛现在有一个长度为 $n$ 的序列，现在牛牛有 $q$ 次询问，每次想询问区间 $[l, r]$ 的 $\tt mex$ 是什么。

一个序列的 $\tt mex$ 定义为最小未出现的自然数。

输入格式

第一行两个整数 $n$，$q$，表示序列长度和询问次数。$n, q \le 10^5$。

接下来一行 $n$ 个非负整数，表示序列 $a_i$。$0 \le a_i < n$，且 $a_i$ 互不相同。

接下来 $q$ 行，每行两个整数 $l$，$r$，表示询问的区间。$1 \le l \le r \le n$。

输出格式

$q$ 行，每行表示询问的答案。

5 2
4 3 0 1 2
2 4
1 5

2
5