$qwq$ 题解满了，没有在线的，这里贴个在线的
思路是一样的，只要保证当前树中相同的数仅存在最靠后的，就可以在线
博客

#include<bits/stdc++.h>
using namespace std;

int read(){int x=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if(c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^48);
    return x*f;
}
const int N = 5e5+10;
const int L = 20;
const int INF = 1e9+10;
const int qwq = 0;
const int qvq = 1;
const int MaxDat = 5e5;

int n,m,pre[N],dat[N];

#define pii pair<int,int>
#define fi first
#define se second
int trcnt,T[N];
struct TREE{
    int ls,rs;
    pii val;
}t[N*L*2];
#define ls(x) t[x].ls
#define rs(x) t[x].rs
void Push_up(int x){t[x].val=min(t[ls(x)].val,t[rs(x)].val);}
int Mdfy(int pr,int x,int a,int b,int seat,int lim){
    if(!x) x=++trcnt,t[x].val.fi=INF;
    if(!(a^b)) return t[x].val.fi=lim,t[x].val.se=a,x;
    int mid=a+b>>1;
    if(seat<=mid) ls(x)=Mdfy(ls(pr),qwq,a,mid,seat,lim),rs(x)=rs(pr);
    else rs(x)=Mdfy(rs(pr),qwq,mid+1,b,seat,lim),ls(x)=ls(pr);
    Push_up(x);
    return x;
}
int Qry(int x,int a,int b,int L,int R){
    if(L<=a&&b<=R) return t[x].val.fi<L?t[x].val.se:INF;
    int mid=a+b>>1,res=INF;
    if(mid>=L) res=min(res,Qry(ls(x),a,mid,L,R)); 
    if(res!=INF) return res; 
    if(mid+1<=R) res=min(res,Qry(rs(x),mid+1,b,L,R));
    return res;
}

signed main(){n=read();
    for(int i=1;i<=n;++i){dat[i]=read();int tmp;
        if(pre[dat[i]]) tmp=Mdfy(T[i-1],qwq,1,MaxDat,pre[dat[i]],INF);
        else tmp=T[i-1];
        T[i]=Mdfy(tmp,qwq,1,MaxDat,i,pre[dat[i]]);
        pre[dat[i]]=i;
    }
    m=read();
    for(int i=1;i<=m;++i){int l=read(),r=read();
        int k=Qry(T[r],1,MaxDat,l,r);
        printf("%d\n",dat[k==INF?0:k]);
    }
    return 0;
}