难度已经远比我能独立做出的题高了。不过回顾一下，几个 trick 的叠加也并非无迹可寻。好题，值得学习。

Hint 1：你能编出一个多项式复杂度做法吗？

看到字典序想到逐位贪心。我们考虑从大到小枚举 $v$，把 $v$ 放在尽可能靠前的位置。

对于每个 $v$，我们按顺序尝试加入所有还没被覆盖的区间。如果加入之后，覆盖这些区间需要的点数 $C\le cnt_v$ 就是合法的。

判断最小覆盖是一个经典贪心问题，每次选择右端点最小的区间，在其右端点处放一个点即可。

Hint 2：每次选出的区间形态如何？

显然是一段前缀，加上一些零散的区间。这看起来是一句废话，但是我们考虑那一段前缀后面一个位置，他不能选说明加入他之后 $C>cnt_v$ 了，而由于 $C$ 的变化是连续的，这说明这个前缀加入之后 $C=cnt_v$。

这样后面的区间就必须满足加入之后，不会增加最小覆盖点数。

Hint 3：如何找到这个前缀？直接二分为什么不可行？

二分意味着我们花了至少序列总长的代价去删除一些元素。因此如果每次只删一个复杂度就起飞了。

但是我们可以考虑先倍增。找到最大的 $2^k$ 满足删除前 $2^k$ 个合法，接下来再在 $[2^k,2^{k+1})$ 内二分，每次暴力跑上面的贪心检验。这样我们就用 $\mathcal O(c\log ^2 c)$ 的代价删除了 $c$ 个元素。总共只删除 $m$ 个元素，因此均摊复杂度正确。

Hint 4：如何判断加入一个区间之后是否需要多一个点覆盖他？

这个结论应该是经典的，可惜我还没见过这样做的题目。有同学知道类似的题目可以在评论区告知我。/kt

我们考虑正反做两遍贪心，求出每个点所在的范围 $[tl_j,tr_j]$。如果 $[L_i,R_i]$ 和某一个 $[tl_j,tr_j]$ 有交，那么可以调整 $j$ 使得不增加新点。反之，需要增加一个点。

Hint 5：一个区间加入之后，$tl,tr$ 会发生怎样的变化？

以 $tr$ 为例。我们找到 $R_i$ 右边第一个 $tr_j$，然后一路向右，如果左端点在前面的，对应的最小右端点不到 $tr_j$ 就会一路修改下去。

这样做的修改次数实际上是 $\mathcal O(c)$ 次，因为 $tr$ 相当于保留一些区间的右端点，而一个右端点存活的时间是一段区间。

Hint 6：利用上面的性质编出正解。

找到前缀后，我们只需要快速找出编号最小的，可以加入的区间。

一个简单的想法是用一个小根堆维护所有的编号。这样我们每次对于一个 $tr_j$，去加入所有和他有交的区间，并贪心跑。

但是这样有一个严重的问题就是，一个区间可能会被放进去很多遍，就退化成 $\mathcal O(nm)$ 了。解决方案也很简单：把所有包含某个 $[tl_j,tr_j]$ 的 $[L_i,R_i]$ 都提前拿出来，这样剩下的区间至多放进去两遍。

找有交的最小编号可以分讨二维偏序关系，用两个线段树维护。

最后整理一下这部分的过程：

• 先得到 $tl,tr$，对于每个 $[tl_j,tr_j]$，先把所有包含他的，还未使用过的区间拎出来标记上。
• 接下来，对于每个 $[tl_j,tr_j]$，找到与其有交的最小编号，加入小根堆。
• 每次取出最小的编号，加入答案。并且重新松弛对应的 $j$，找到新的最小值。

最终时间复杂度为 $\mathcal O(n\log^2 n)$，可以通过预处理排序做到 $\mathcal O(n\log n)$。

实现上细节比较多，一定要理清楚再开始写，写完一部分 debug 掉对应的问题。参考代码。

#pragma GCC optimize(2,3,"Ofast","inline","unroll-loops")
#pragma GCC optimize("-Ofast", "-finline", "-funroll-loops", "-fno-stack-protector")
#include<bits/stdc++.h>
#define debug(x) cerr<<(#x)<<": "<<x<<endl
typedef int ll;
typedef long double ld;
typedef unsigned long long ull;
#define pii pair<ll,ll>
#define rep(i,a,b) for(ll i=(a);i<=(b);++i)
#define per(i,a,b) for(ll i=(a);i>=(b);--i)
using namespace std;
bool Mbe;
ll read(){
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
void write(ll x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const ll N=1e5+9,INF=1e9;
ll n,m,Lf,L[N],R[N],cnt[N],ans[N],Len;
struct DSU{
    ll fa[N];
    void init(){
        iota(fa,fa+m+1,0ll);
    }
    ll find(ll x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void del(ll x){fa[x]=x+1;}
    vector<ll> getseg(ll c){
        ll u=find(1);
        vector<ll> vec;
        while(c)vec.push_back(u),u=find(u+1),c--;
        return vec;
    }
}D;
pair<vector<ll>,vector<ll> > work_work(vector<ll>v){
    vector<ll> vL,vR;
    sort(v.begin(),v.end(),[&](ll i,ll j){
        return R[i]<R[j]||(R[i]==R[j]&&L[i]<L[j]);
    });
    ll cur=0;
    rep(i,0,(ll)v.size()-1){
        ll id=v[i];
        if(L[id]>cur)vR.push_back(R[id]),cur=R[id];
    }
    sort(v.begin(),v.end(),[&](ll i,ll j){
        return L[i]>L[j]||(L[i]==L[j]&&R[i]>R[j]);
    });
    cur=n+1;
    rep(i,0,(ll)v.size()-1){
        ll id=v[i];
        if(R[id]<cur)vL.push_back(L[id]),cur=L[id];
    }
    assert(vL.size()==vR.size());
    reverse(vL.begin(),vL.end());
    return make_pair(vL,vR);
}
struct BIT{
    ll bit[N],stk[N],top;
    void Init(){
        rep(i,0,n+1)bit[i]=INF;
        top=0;
    }
    void Upd(ll x,ll k){
        stk[++top]=x;
        while(x)bit[x]=min(bit[x],k),x-=(x&(-x));
    }
    void Clr(ll x){
        while(x)bit[x]=INF,x-=(x&(-x));
    }
    ll Query(ll x){
        ll res=INF;
        while(x<=n)res=min(res,bit[x]),x+=(x&(-x));
        return res;
    }
    void Retreat(){
        while(top)Clr(stk[top]),top--;
    }
};
BIT bL,bR;
vector<ll>vL,vR,remov;
ll pL[N],pR[N];
bool exs[N];
struct Seg{
    ll tr[N<<2];
    vector<ll>v1[N],v2[N<<2];
    ll M1(ll x){
        while(!v1[x].empty()&&!exs[v1[x].back()])v1[x].pop_back();
        if(v1[x].empty())return INF;
        return v1[x].back();
    }
    ll M2(ll x){
        while(!v2[x].empty()&&!exs[v2[x].back()])v2[x].pop_back();
        if(v2[x].empty())return INF;
        return v2[x].back();
    }
    void Build(ll x,ll l,ll r){
        tr[x]=INF,v2[x].clear();
        if(l==r)return v1[l].clear(),void();
        ll mid=(l+r)>>1;
        Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
    }
    void Upd1(ll x,ll l,ll r,ll u,ll v){
        if(l==r)return v1[u].push_back(v),tr[x]=M1(u),void();
        ll mid=(l+r)>>1;
        if(u<=mid)Upd1(x<<1,l,mid,u,v);
        else Upd1(x<<1|1,mid+1,r,u,v);
        tr[x]=min(tr[x<<1],tr[x<<1|1]);
    }
    void Remake(ll x,ll l,ll r,ll u){
        if(l==r)return tr[x]=M1(u),void();
        ll mid=(l+r)>>1;
        if(u<=mid)Remake(x<<1,l,mid,u);
        else Remake(x<<1|1,mid+1,r,u);
        tr[x]=min(tr[x<<1],tr[x<<1|1]);
    }
    void Upd2(ll x,ll l,ll r,ll ql,ll qr,ll v){
        if(ql<=l&&r<=qr)return v2[x].push_back(v),void();
        ll mid=(l+r)>>1;
        if(ql<=mid)Upd2(x<<1,l,mid,ql,qr,v);
        if(qr>mid)Upd2(x<<1|1,mid+1,r,ql,qr,v);
    }
    ll Query(ll x,ll l,ll r,ll ql,ll qr){
        if(ql<=l&&r<=qr)return tr[x];
        ll mid=(l+r)>>1;
        if(qr<=mid)return Query(x<<1,l,mid,ql,qr);
        if(ql>mid)return Query(x<<1|1,mid+1,r,ql,qr);
        return min(Query(x<<1,l,mid,ql,qr),Query(x<<1|1,mid+1,r,ql,qr));
    }
    ll Qsingle(ll x,ll l,ll r,ll u){
        if(l==r)return M2(x);
        ll mid=(l+r)>>1;
        if(u<=mid)return min(M2(x),Qsingle(x<<1,l,mid,u));
        return min(M2(x),Qsingle(x<<1|1,mid+1,r,u));
    }
    ll Query(ll l,ll r){
        return min(Qsingle(1,1,n,l),Query(1,1,n,l,r));
    }
    void Del(ll x){
        assert(exs[x]);
        exs[x]=0;
        Remake(1,1,n,L[x]);
    }
}T;
bool Full(ll l,ll r){
    ll p=lower_bound(pL,pL+Len,l)-pL;
    return p<Len&&r>=pR[p];
}
bool Intersect(ll l,ll r){
    ll p=lower_bound(pL,pL+Len,l)-pL;
    if(p<Len&&r>=pL[p])return 1;
    if(p&&l<=pR[p-1])return 1;
    return 0;
}
priority_queue<pii,vector<pii>,greater<pii> > Q;
ll cur_V;
void Modify(ll x){
    ll mn=T.Query(pL[x],pR[x]);
    while(mn!=INF&&Full(L[mn],R[mn])){
        remov.push_back(mn),ans[mn]=cur_V,Lf--;
        T.Del(mn);
        mn=T.Query(pL[x],pR[x]);
    }
    if(mn!=INF)Q.push({mn,x});
}
void Set_L(ll p,ll v){
    pL[Len-p-1]=n-v+1,Modify(Len-p-1);
}
void Set_R(ll p,ll v){
    pR[p]=v,Modify(p);
}
void Ins_L(ll l,ll r){
    bL.Upd(l,r);
    ll p=upper_bound(vL.begin(),vL.end(),r)-vL.begin();
    ll nxt=bL.Query(p?vL[p-1]+1:1);
    while(p<(ll)vL.size()&&nxt<vL[p]){
        vL[p]=nxt,Set_L(p,nxt);
        p++,nxt=bL.Query(nxt+1);
    }
}
void Ins_R(ll l,ll r){
    bR.Upd(l,r);
    ll p=upper_bound(vR.begin(),vR.end(),r)-vR.begin();
    ll nxt=bR.Query(p?vR[p-1]+1:1);
    while(p<(ll)vR.size()&&nxt<vR[p]){
        vR[p]=nxt,Set_R(p,nxt);
        p++,nxt=bR.Query(nxt+1);
    }
}
bool Med;
int main(){
    cerr<<fabs(&Med-&Mbe)/1048576.0<<"MB\n";
    n=read(),m=read();
    rep(i,1,n)cnt[read()]++;
    rep(i,1,m)L[i]=read(),R[i]=read();
    fill(exs+1,exs+m+1,1);
    D.init(),Lf=m;
    T.Build(1,1,n);
    per(i,m,1){
        T.Upd1(1,1,n,L[i],i);
        T.Upd2(1,1,n,L[i],R[i],i);
    }
    bL.Init(),bR.Init();
    per(V,n,1){
        if(!Lf)break;
        if(!cnt[V])continue;
        cur_V=V;
        ll k=0;
        while((1<<k)<=Lf&&(ll)work_work(D.getseg(1<<k)).first.size()<=cnt[V])k++;
        ll l=1<<(k-1),r=min(Lf,(1<<k)-1),bst=1<<(k-1);
        while(l<=r){
            ll mid=(l+r)>>1;
            if((ll)work_work(D.getseg(mid)).first.size()<=cnt[V])bst=mid,l=mid+1;
            else r=mid-1;
        }
        vector<ll> cid=D.getseg(bst);
        remov.clear();
        pair<vector<ll>,vector<ll> > chosen=work_work(cid);
        vL=chosen.first,vR=chosen.second;
        Len=vL.size();
        rep(i,0,Len-1)pL[i]=vL[i],pR[i]=vR[i];
        reverse(vL.begin(),vL.end());
        rep(i,0,Len-1)vL[i]=n-vL[i]+1;
        for(ll x:cid)D.del(x),ans[x]=V,Lf--,T.Del(x);
        rep(i,0,Len-1)Modify(i);
        for(ll x:cid)bR.Upd(L[x],R[x]);
        reverse(cid.begin(),cid.end());
        for(ll x:cid)bL.Upd(n-R[x]+1,n-L[x]+1);
        while(!Q.empty()){
            pii now=Q.top();Q.pop();
            ll id=now.first,bel=now.second;
            if(!ans[id]&&Intersect(L[id],R[id])){
                ans[id]=V,Lf--,T.Del(id);
                Ins_R(L[id],R[id]),Ins_L(n-R[id]+1,n-L[id]+1);
                remov.push_back(id);
            }
            Modify(bel);
        }
        bL.Retreat(),bR.Retreat();
        for(ll x:remov)D.del(x);
    }
    rep(i,1,m)write(ans[i]),putchar('\n');
    cerr<<"\n"<<clock()*1.0/CLOCKS_PER_SEC*1000<<"ms\n";
    return 0;
}