注意到答案最终由询问右端点处统计，也就是说我们只需要维护这些点上的ans即可，然后纯二分过了？

2.52s -O2

#include <bits/stdc++.h>
#define MAXN 200003
using namespace std;
int n,m;
int a[MAXN];
int vis[MAXN];
int ans[MAXN];
int lst[MAXN],nxt[MAXN];
struct Query{
    int l;
    int r;
    int id;
    bool operator<(const Query &B)const{
        if (l==B.l) return r<B.r;
        else return l<B.l;
    }
}Q[MAXN];
int inn[MAXN];
int upd[MAXN],cnt;
int ANS[MAXN];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<=m;i++) {cin>>Q[i].l>>Q[i].r; Q[i].id=i; inn[Q[i].r]=1;}
    for (int i=1;i<=200000;i++) if (inn[i]) upd[++cnt]=i;
    sort(Q+1,Q+1+m);
    for (int i=1;i<=n;i++){
        vis[a[i]]=1;
        ans[i]=ans[i-1];
        while (vis[ans[i]]) ans[i]++;
    }
    for (int i=n;i>=1;i--){
        if (!lst[a[i]]) nxt[i]=n+1;
        else nxt[i]=lst[a[i]];
        lst[a[i]]=i;
    }
    int nowl=1;
    for (int i=1;i<=m;i++){
        while (nowl<Q[i].l){
            int l=nowl+1,r=nxt[nowl]-1;
            while (l<r){
                int mid=(l+r)>>1;
                if (ans[mid]<a[nowl]) l=mid+1;
                else r=mid;
            }
            int L,R;
            L=lower_bound(upd+1,upd+1+cnt,l)-upd;
            R=upper_bound(upd+L,upd+1+cnt,nxt[nowl]-1)-upd-1;
            for (int j=L;j<=R;j++){
                ans[upd[j]]=min(ans[upd[j]],a[nowl]);
            }
            nowl++;
        }
        ANS[Q[i].id]=ans[Q[i].r];
    }
    for (int i=1;i<=m;i++) cout<<ANS[i]<<'\n';
    return 0;
}