#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) (i&-i)
#define double long double
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5e5+5,M=15,S=(1<<8)+5,inf=(ll)1e18+7,mo=1e9+7;
const double eps=1e-8;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int n,m,a[N],ans[N];
struct query{
    int id,l,r;
    friend bool operator<(query x,query y){
        if(x.l==y.l)return x.r>y.r;
        return x.l<y.l;
    }
}q[N];
struct BIT{
    int t[N];
    void add(int x,int v){
        for(int i=x;i<=n;i+=lowbit(i))
            t[i]+=v;
    }
    int query(int x){
        int res=0;
        for(int i=x;i;i-=lowbit(i))
            res+=t[i];
        return res;
    }
}BIT;
struct seg{
    pii t[4*N];
    int tag[4*N];
    void pushup(int x){
        if(t[ls(x)].fir>=t[rs(x)].fir)t[x]=t[ls(x)];
        else t[x]=t[rs(x)];
    }
    void build(int x,int le,int ri){
        tag[x]=0;
        if(le==ri){
            t[x]=mp(-inf,le);
            return;
        }
        int mid=(le+ri)>>1;
        build(ls(x),le,mid),build(rs(x),mid+1,ri);
        pushup(x);
    }
    void pushdown(int x){
        t[ls(x)].fir+=tag[x],t[rs(x)].fir+=tag[x];
        tag[ls(x)]+=tag[x],tag[rs(x)]+=tag[x];
        tag[x]=0;
    }
    void modify(int x,int le,int ri,int p,int v){
        if(le==ri){
            t[x].fir=v;
            return;
        }
        pushdown(x);
        int mid=(le+ri)>>1;
        if(p<=mid)modify(ls(x),le,mid,p,v);
        else modify(rs(x),mid+1,ri,p,v);
        pushup(x);
    }
    void add(int x,int le,int ri,int ql,int qr,int v){
        if(ql>qr)return;
        if(ql<=le&&qr>=ri){
            t[x].fir+=v,tag[x]+=v;
            return;
        }
        pushdown(x);
        int mid=(le+ri)>>1;
        if(ql<=mid)add(ls(x),le,mid,ql,qr,v);
        if(qr>mid)add(rs(x),mid+1,ri,ql,qr,v);
        pushup(x);
    }
    pii query(int x,int le,int ri,int ql,int qr){
        if(ql<=le&&qr>=ri)return t[x];
        pushdown(x);
        int mid=(le+ri)>>1;
        pii resl=mp(-inf,0),resr=mp(-inf,0);
        if(ql<=mid)resl=query(ls(x),le,mid,ql,qr);
        if(qr>mid)resr=query(rs(x),mid+1,ri,ql,qr);
        if(resl.fir>=resr.fir)return resl;
        return resr;
    }
}T1,T2;
set<pii>sl,sr;
vector<int>pos[N];
void update(int le,int ri,int lar){
    while(le<=ri){
        pii res=T2.query(1,1,m,le,ri);
        if(res.fir<=lar)break;
        int nid=res.sec;
        ri=nid-1;
        //printf("update:%lld\n",nid);
        int nwv=BIT.query(q[nid].r)-BIT.query(q[nid].l-1);
        T1.modify(1,1,m,nid,nwv),T2.modify(1,1,m,nid,-inf);
        sl.insert(mp(q[nid].l,nid)),sr.insert(mp(q[nid].r,nid));
    }
}
signed main(){
    read(n),read(m);
    int upp=0;
    rep(i,1,n)
        read(a[i]),BIT.add(i,1),pos[a[i]].push_back(i),upp=max(upp,a[i]);
    rep(i,1,m)
        read(q[i].l),read(q[i].r),q[i].id=i;
    sort(q+1,q+m+1);
    T1.build(1,1,m),T2.build(1,1,m);
    rep(i,1,m)
        T2.modify(1,1,m,i,q[i].r);
    update(1,m,0);
    repp(i,upp,0){
        //printf("start:%lld\n",i);
        while(T1.t[1].fir>i){
            int nid=T1.t[1].sec,ql=0,qr=0;
            //printf("%lld,nid:%lld\n",i,nid);
            fflush(stdout);
            T1.modify(1,1,m,nid,-inf);
            ans[q[nid].id]=i+1;
            set<pii>::iterator it=sr.lower_bound(mp(q[nid].r,nid));
            it++;
            if(it!=sr.end())qr=it->sec;
            else qr=m+1;
            it--;
            if(it!=sr.begin())it--,ql=it->fir;
            else ql=0;
            sl.erase(mp(q[nid].l,nid));
            sr.erase(mp(q[nid].r,nid));
            update(nid+1,qr-1,ql);
        }
        //printf("!%lld\n",i);
        fflush(stdout);
        for(auto j:pos[i]){
            set<pii>::iterator it;
            int ql=0,qr=0;
            it=sl.upper_bound(mp(j,inf));
            if(it==sl.begin())continue;
            it--,qr=it->sec;
            it=sr.lower_bound(mp(j,0));
            if(it==sr.end())continue;
            ql=it->sec;
            //printf("add:%lld %lld\n",ql,qr);
            T1.add(1,1,m,ql,qr,-1);
            BIT.add(j,-1);
        }
    }
    rep(i,1,m)
        printf("%lld\n",ans[i]);
    return 0;
}