Description：

多次询问某个区间中最小没有出现过的非负整数，可以离线。

$1\leqslant n\leqslant 200000$

Solution：

莫队经典题，先离散化，注意离散化的时候如果隔了大于等于一个要在中间插一个，然后记录一个某个数出现的个数，然后增加的时候 $ans$ 可能增加，这个时候单次是最差 $O(n)$ 的，删除的时候 $ans$ 可能变小，但是发现每次 $O(n)$ 增加的时候这些位置都必须有值，因此均摊是 $O(1)$ 的。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 400010

int a[MAXN],b[MAXN];

int cnt[MAXN];

int tot = 0;

int val[MAXN];

struct query

{

	int l,r,id,ans;

}q[MAXN];

int pos[MAXN];

bool cmp(query a,query b){return (pos[a.l] == pos[b.l] ? a.r < b.r : pos[a.l] < pos[b.l]);}

bool cmp_id(query a,query b){return a.id < b.id;}

int ans = 1;

void inc(int p)

{

	++cnt[a[p]];

	while(cnt[ans] != 0)++ans;

	return;

}

void dec(int p)

{

	--cnt[a[p]];

	if(cnt[a[p]] == 0 && a[p] < ans)ans = a[p];

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)b[i] = a[i];

	sort(b + 1,b + 1 + n);

	for(int i = 1;i <= n;++i)

	{

		if(i != 1 && b[i] == b[i - 1])continue;

		if(i == 1 || b[i] == b[i - 1] + 1)val[++tot] = b[i];

		else

		{

			val[++tot] = b[i - 1] + 1;

			val[++tot] = b[i];

		}

	}

	val[++tot] = b[n] + 1;

	for(int i = 1;i <= n;++i)a[i] = lower_bound(val + 1,val + 1 + tot,a[i]) - val;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d",&q[i].l,&q[i].r);

		q[i].id = i;

	}

	int blo = sqrt(n);

	for(int i = 1;i <= n;++i)pos[i] = (i - 1) / blo + 1;

	sort(q + 1,q + 1 + m,cmp);

	for(int i = 1,l = 1,r = 0;i <= m;++i)

	{

		for(;r < q[i].r;++r)inc(r + 1);

		for(;l > q[i].l;--l)inc(l - 1);

		for(;r > q[i].r;--r)dec(r);

		for(;l < q[i].l;++l)dec(l);

		q[i].ans = ans;

	}

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)printf("%d\n",val[q[i].ans]);

	return 0;

}