这底下的 fo(i,1,n) 就是 for(register int i=1;i<=n;i++。

个人因为懒喜欢宏定义。

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(register int v=a;v<=b;v++)
#define fr(v,a,b) for(register int v=a;v>=b;v--)
#define il inline

int read(){
    int s=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=s*10+ch-'0';
        ch=getchar();
    }
    return s*f;
}

const int N=200010,M=400010;
const int SN=1010;

int n,m,a[N];
int b[M],tot;

struct query
{
	int id;
	int l,r;
}q[N];

int T,B,bel[N];//belong
int L[SN],R[SN];
bool cmp(query C,query D)
{	return bel[C.l]==bel[D.l]?C.r<D.r:bel[C.l]<bel[D.l];	}

void prework()
{
	T=sqrt(n);B=n/T;
	fo(i,1,n) bel[i]=(i-1)/T+1;
	fo(i,1,B) L[i]=R[i-1]+1,R[i]=i*T;
	if(R[B]<n) {
		B++;
		L[B]=R[B-1]+1,R[B]=n;
	}
}

int ans[N];

int cnt[M],cur;
il void add(int x)
{
	cnt[a[x]]++;
	if(cur==a[x])
		while(cur<tot&&cnt[cur])
			cur++;
}
il void del(int x)
{	cnt[a[x]]--;	}

int Cnt[M];
void bf(int x)
{
	int Ans=1;
	fo(i,q[x].l,q[x].r)
	{
		Cnt[a[i]]++;
		if(Ans==a[i])
			while(Ans<tot&&Cnt[Ans])
				Ans++;
	}
	fo(i,q[x].l,q[x].r)Cnt[a[i]]--;
	ans[q[x].id]=b[Ans];
}

int main()
{
	n=read(),m=read();
	fo(i,1,n) a[i]=read();
	
	b[tot=1]=0;
	fo(i,1,n) b[++tot]=a[i],b[++tot]=a[i]+1;
	sort(b+1,b+tot+1);
	tot=unique(b+1,b+tot+1)-(b+1);
	fo(i,1,n) a[i]=lower_bound(b+1,b+tot+1,a[i])-b;

	fo(i,1,m) q[i].l=read(),q[i].r=read(),q[i].id=i;
	
	prework();
	sort(q+1,q+m+1,cmp);
	
	int l,r,i=1;//b[1]=0
	fo(k,1,B)
	{
		if(bel[q[i].l]!=k) continue;

		l=R[k],r=l-1,cur=1;
		memset(cnt,0,sizeof(cnt));
		
		for(;bel[q[i].l]==k;i++)
		{
			if(bel[q[i].l]==bel[q[i].r])
			{	bf(i);continue;		}
			
			//solve
			while(r<q[i].r) add(++r);
			int tmp=cur;
			while(l>q[i].l) add(--l);
			ans[q[i].id]=b[cur];
			//clear
			while(l<R[k]) del(l++);
			cur=tmp;
		}
	}
	
	fo(j,1,m) printf("%d\n",ans[j]);
	
    return 0;
}