#include<bits/stdc++.h>
using namespace std;
int root[200009];
int currNodes=0;
struct Node
{
int l,r;
int v;
};
Node tree[4000000];
int build(int l,int r)
{
int curr=++currNodes;
if(l==r)
{
tree[curr].v=0;
tree[curr].l=-1;
tree[curr].r=-1;
return curr;
}
tree[curr].v=0;
tree[curr].l=build(l,(l+r)/2);
tree[curr].r=build((l+r)/2+1,r);
return curr;
}
int change(int n,int currL,int currR,int t)
{
int curr=++currNodes;
tree[curr]=tree[n];
tree[curr].v++;
if(currL==currR)
{
return curr;
}
int mid=(currL+currR)/2;
if(t<=mid)
{
tree[curr].l=change(tree[curr].l,currL,mid,t);
}
else
{
tree[curr].r=change(tree[curr].r,mid+1,currR,t);
}
return curr;
}
int walk(int n1,int n2,int currL,int currR,int currSum)
{
if(currL==currR)
{
if(tree[n2].v-tree[n1].v+currSum>=currL)return currL;
return -1;
}
int mid=(currL+currR)/2;
if(currSum+tree[tree[n2].r].v-tree[tree[n1].r].v>=mid+1)
{
return walk(tree[n1].r,tree[n2].r,mid+1,currR,currSum);
}
else
{
return walk(tree[n1].l,tree[n2].l,currL,mid,currSum+tree[tree[n2].r].v-tree[tree[n1].r].v);
}
return -1;
}
signed main ()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
root[0]=build(1,200000);
long long N,Q,a,l,r;
cin>>N>>Q;
for(int i=1;i<=N;i++)
{
cin>>a;
root[i]=change(root[i-1],1,200000,a);
}
while(Q--)
{
cin>>l>>r;
cout<<walk(root[l-1],root[r],1,200000,0)<<'\n';
}
return 0;
}
