#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int N=5e5+10,M=N<<2;
int n,m,a[N],ans[N];
vector<int> p[N];
struct que{int l,r,id;}q[N];
namespace BIT{
int t[N];
#define lbt(x) (x&-x)
void add(int x,int k){for(;x<=n;x+=lbt(x)) t[x]+=k;}
int ask(int x){int r=0;for(;x;x-=lbt(x)) r+=t[x];return r;}
}
bool vis[N];
#define ls x<<1
#define rs x<<1|1
#define mid ((l+r)>>1)
int t[M],tg[M],mnl[M],mxl[M],mnr[M],mxr[M],mx[M];
void upd(int x,int k){t[x]+=k;tg[x]+=k;}
void pushdown(int x){if(tg[x]) upd(ls,tg[x]),upd(rs,tg[x]),tg[x]=0;}
void pushup(int x){t[x]=max(t[ls],t[rs]);mx[x]=max(mx[ls],mx[rs]);mnl[x]=min(mnl[ls],mnl[rs]);mxl[x]=max(mxl[ls],mxl[rs]);mnr[x]=min(mnr[ls],mnr[rs]);mxr[x]=max(mxr[ls],mxr[rs]);}
void build(int x,int l,int r){if(l==r) return t[x]=-1,mnl[x]=n+1,mnr[x]=n+1,mx[x]=q[l].r,void();build(ls,l,mid);build(rs,mid+1,r);pushup(x);}
void update(int x,int l,int r,int id){if(mnl[x]>id||mxr[x]<id) return;if(mxl[x]<=id&&id<=mnr[x]) return upd(x,-1);pushdown(x);update(ls,l,mid,id);update(rs,mid+1,r,id);pushup(x);}
bool check(int x,int l,int r,int k,int &mr){
	if(r<=k) return mr=max(mr,mx[x]),1;
	if(mx[x]<=mr) return 1;
	if(l==r){
		if(vis[l]) return 0;vis[l]=1;
		t[x]=BIT::ask(q[l].r)-BIT::ask(q[l].l-1);
		mnl[x]=mxl[x]=q[l].l;
		mr=mx[x]=mnr[x]=mxr[x]=q[l].r;
		return 1;
	}
	pushdown(x);
	if(!check(ls,l,mid,k,mr)) return pushup(x),0;
	bool fl=check(rs,mid+1,r,k,mr);return pushup(x),fl;
}
int find(int x,int l,int r,int k){
	if(t[x]<k) return -1;
	if(l==r) return t[x]=-1,mx[x]=0,l;
	pushdown(x);int ans=find(ls,l,mid,k);if(~ans) return pushup(x),ans;
	ans=find(rs,mid+1,r,k);pushup(x);return ans;
}
int main(){
    scanf("%d%d",&n,&m);rep(i,1,n) scanf("%d",a+i),p[a[i]].push_back(i),BIT::add(i,1);
    rep(i,1,m) scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;sort(q+1,q+m+1,[](que A,que B){return A.l<B.l||(A.l==B.l&&A.r>B.r);});
	build(1,1,n);int kk=0;check(1,1,n,0,kk);per(k,n,1){
		for(int x:p[k]) BIT::add(x,-1),update(1,1,n,x);
		int p;while(~(p=find(1,1,n,k))) ans[q[p].id]=k,kk=0,check(1,1,n,0,kk);
	}
    rep(i,1,m) printf("%d\n",ans[i]);
    return 0;
}