对于每一个a[i],mex可以是a[i],a[i+1],0,用一个数组b来存，如何将离散化、
线段树需要维护下标，而不是mex本身，所以sum，应当等于下标（a数组的下标），插入位置应该是
对于没一个询问，即[l,r]中的mex，取[1,l]中的最小权值即为答案（当然，这是下标）
#include <bits/stdc++.h>
#define inf 0x7fffffff
#define ll long long
#define int long long
//#define double long double
//#define double long long
#define re register int
//#define void inline void
#define eps 1e-8
//#define mod 1e9+7
#define ls(p) p<<1
#define rs(p) p<<1|1
#define pi acos(-1.0)
#define pb push_back
#define mk make_pair
#define P pair < int , int >
using namespace std;
const int mod= 998244353;
//const int inf=1e18;
const int M=1e8;
const int N=2e5+5;//??????.???? 4e8
struct node
{
int l,r,sum;
}e[N*80];
int tot,a[N],b[N],rt[N];
int n,m,q;
void insert(int &p,int pre,int l,int r,int pos,int val)
{
e[++tot]=e[pre];
p=tot;
if(l==r)
{
e[p].sum=val;
return;
}
int mid=(l+r)>>1;
if(pos<=mid) insert(e[p].l,e[pre].l,l,mid,pos,val);
else insert(e[p].r,e[pre].r,mid+1,r,pos,val);
e[p].sum=min(e[e[p].l].sum,e[e[p].r].sum);
}
int ask(int p,int l,int r,int val)
{
if(l==r) return l;
int mid=(l+r)>>1;
int t=e[e[p].l].sum;
if(t<val) return ask(e[p].l,l,mid,val);//注意这里 ,左子树，且是小于
else return ask(e[p].r,mid+1,r,val);
}
void solve()
{
int cnt=0;
cin>>n>>q;
for(re i=1;i<=n;i++) scanf("%lld",&a[i]),b[++cnt]=a[i],b[++cnt]=a[i]+1;
b[++cnt]=0;
sort(b+1,b+cnt+1);
m=unique(b+1,b+cnt+1)-(b+1);
for(re i=1;i<=n;i++) insert(rt[i],rt[i-1],1,m,lower_bound(b+1,b+m+1,a[i])-b,i);
while(q--)
{
int l,r;
scanf("%lld%lld",&l,&r);
printf("%lld\n",b[ask(rt[r],1,m,l)]);
}
}
signed main()
{
int T=1;
// cin>>T;
for(int index=1;index<=T;index++)
{
solve();
// puts("");
}
return 0;
}
/*
*/