题目描述
给出一个长度为 n 的序列,现在给出 Q 次询问,每次询问给出一个区间 [l,r] ,你需要回答区间 [l,r] 中的数的 mex 是什么。
一个集合的 mex 定义为最小未出现的自然数,比如 mex(0,1,3)=2,mex(1,2,3)=0。
请注意本题的数据范围。
输入格式
第一行两个整数 n,q 表示序列长度和询问次数。
接下来一行 n 个非负整数表示序列 ai。
接下来 q 行,每行两个整数 li,ri 表示这一次询问的区间。
输出格式
输出 q 行,每行一个非负整数,表示这次询问的答案。
样例 1 输入
5 2
4 3 0 1 2
2 4
1 5
样例 1 输出
2
5
数据范围
对于 20% 的数据,n≤3×102。
对于 50% 的数据,n≤5×103。
对于 70% 的数据,n≤5×104。
对于 100% 的数据,1≤n,q≤2×105,0≤ai<n 且 ai 互不相同。