题解：
先离散化，然后插一堆空白，大体就是如果（对于以a.data<b.data排序后的A）A[i-1].data+1!=A[i].data，则插一个空白叫做A[i-1].data+1，
开头和最尾也要这么插，意义是如果取不了A[i-1]了，最早能取的是啥数。要把这些空白也离散化然后扔主席树里啊。
主席树维护每个数A[i]出现的最晚位置（tree[i].data），查询时查询root[R]的树中最早的data<L的节点（这意味着该节点的下标离散化前代
表的数没有在区间L到R中）。
顺带一提，这道题也可以用莫队套分块做，原理十分好理解，分块维护的是权值，块[i]维护该块是否被填满。我也扔了代码。
另外，我主席树的空间开的其实是不对的，但是bzoj空间比较卡，所以开小点理论上是不对的，但是数据没有那么极端而已。
代码：
主席树||可持久化线段树+离散化版：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=+,maxm=+,inf=<<;
int N,M,cor[maxn<<],lsh_cnt=,root[maxn<<],num_treenode=,L,R;
bool pb[maxn<<];
struct _A{int id,yn,data;}A[maxn];
inline bool cmp(const _A&a,const _A&b){return a.yn<b.yn;}
struct Tree{
int l,r,data,ls,rs;
}t[maxn*];
inline void Build(int x,int l,int r){
t[x].l=l;t[x].r=r;int mid=(l+r)>>;
if(l==r){
if(pb[l])t[x].data=;
return;
}
Build(t[x].ls=++num_treenode,l,mid);
Build(t[x].rs=++num_treenode,mid+,r);
return;
}
inline void Update(int u,int x,int q,int s){
int l=t[u].l,r=t[u].r,mid=(l+r)>>,ls=t[u].ls,rs=t[u].rs;
t[x].l=l;t[x].r=r;
if(l==r&&l==q){t[x].data=s; return;}
if(q<=mid){t[x].rs=rs; Update(ls,t[x].ls=++num_treenode,q,s);}
else{t[x].ls=ls; Update(rs,t[x].rs=++num_treenode,q,s);}
ls=t[x].ls;rs=t[x].rs;
t[x].data=min(t[ls].data,t[rs].data);
return;
}
inline int Query(int x,int s){
int l=t[x].l,r=t[x].r,ls=t[x].ls,rs=t[x].rs;
if(l==r)return l;
if(t[ls].data<s)return Query(ls,s);else return Query(rs,s);
}
inline bool cmp2(const _A&a,const _A&b){return a.id<b.id;}
int main(){
N=rd();M=rd();
for(int i=;i<=N;i++){A[i].yn=rd();A[i].id=i;}
sort(A+,A+N+,cmp);
if(A[].yn!=){
cor[++lsh_cnt]=;
pb[lsh_cnt]=;
}
A[].data=++lsh_cnt;
cor[lsh_cnt]=A[].yn;
for(int i=;i<=N;i++)
if(A[i].yn!=A[i-].yn){
if(A[i].yn!=A[i-].yn+){
cor[++lsh_cnt]=A[i-].yn+;
pb[lsh_cnt]=;
}
A[i].data=++lsh_cnt;
cor[lsh_cnt]=A[i].yn;
}
else A[i].data=lsh_cnt;
cor[++lsh_cnt]=A[N].yn+;
pb[lsh_cnt]=;
Build(root[]=++num_treenode,,lsh_cnt);
sort(A+,A+N+,cmp2);
for(int i=;i<=N;i++)
Update(root[i-],root[i]=++num_treenode,A[i].data,A[i].id);
while(M--){
L=rd();R=rd();
printf("%d\n",cor[Query(root[R],L)]);
}
return ;
}
莫队套分块版：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
inline int rd(){
int f=,x=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=,maxm=,max_block=;
int N,M,A[maxn],l,r,block,Ans[maxm],vis[maxn],cnt[max_block],num,belong[maxn];
struct Q{
int id,l,r;
}q[maxm];
inline bool cmp(const Q&a,const Q&b){
if(belong[a.l]==belong[b.l])return a.r<b.r;
return a.l<b.l;
}
inline void Add(int x){
if(x<=N){
if(vis[x]==)cnt[belong[x]]++;
vis[x]++;
}
return;
}
inline void Del(int x){
if(x<=N){
vis[x]--;
if(vis[x]==)cnt[belong[x]]--;
}
return;
}
int main(){
N=rd();M=rd();
block=sqrt(N);
num=N/block;
if(N%block)num++;
for(int i=;i<=N;i++){
A[i]=rd();
belong[i]=(i-)/block+;
}
belong[]=;
for(int i=;i<=M;i++){
q[i].id=i;
q[i].l=rd();
q[i].r=rd();
}
sort(q+,q+M+,cmp);
l=;r=;
for(int i=;i<=M;i++){
int ql=q[i].l,qr=q[i].r,id=q[i].id;
while(l<ql)Del(A[l++]);
while(l>ql)Add(A[--l]);
while(r<qr)Add(A[++r]);
while(r>qr)Del(A[r--]);
if(cnt[]==){
Ans[id]=;
continue;
}
int t=-;
for(int j=;j<=num;j++){
if(j!=num&&cnt[j]!=block){
t=j;
break;
}
else if(cnt[j]!=N-(num-)*block) t=j;
}
if(t==-){
Ans[id]=N;
continue;
}
int f=(t-)*block+,toj=t*block;
for(int j=f;j<=toj;j++)
if(vis[j]==){
Ans[id]=j;
break;
}
}
for(int i=;i<=M;i++)printf("%d\n",Ans[i]);
return ;
}
By:AlenaNuna