#include <bits/stdc++.h>
using namespace std;
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define int long long int
#define endl '\n'
#define N 200105
#define MM 200000
#define mod 1000000007
#define pb push_back
#define p push
#define ins insert
#define f first
#define s second
//persistent segment tree kodu ///////////////////////////////////////////////////////////////////////////////////////////////////
int n;
struct node{
node *left, *right;
int val;
node(node* a,node* b){
val=0;
left=a;
right=b;
if(a) val+=a->val;
if(b) val+=b->val;
}
node(){
val=0;
left=NULL;right=NULL;
}
};
vector<node*> baslar;
node* update(node* x,int l,int r,int hed){
if(l==r){
node* yeni=new node;
yeni->val=x->val+1;
return yeni;
}
if(x->left==NULL)x->left=new node;
if(x->right==NULL)x->right=new node;
int mid=(l+r)/2;
if(hed<=mid){
return new node(update(x->left,l,mid,hed),x->right);
}
return new node(x->left,update(x->right,mid+1,r,hed));
}
inline int qua(node* x,int l,int r,int s,int e){
if(l>r||s>r||e<l||x==NULL) return 0;
if(s<=l&&r<=e)return x->val;
int mid=(l+r)/2;
return qua(x->left, l,mid,s,e)+qua(x->right,mid+1,r,s,e);
}
int cev(int x,int y){
int l=1,r=n;
int yes=-1;
while(l<=r){
int mid=(l+r)/2;
int a=qua(baslar[x-1],1,MM,1,MM-mid+1);
int b=qua(baslar[y],1,MM,1,MM-mid+1);
//cout<<l<<" "<<r<<" "<<mid<<" "<<a<<" "<<b<<endl;
if(b-a>=mid){
yes=mid;
l=mid+1;
}
else r=mid-1;
}
return yes;
}
signed main(){
lalala;
node* bas=new node;
baslar.pb(bas);
int q;cin>>n>>q;
for(int i=1;i<=n;i++){
int x;cin>>x;
int y=MM-x+1;
node* yeni=update(baslar[baslar.size()-1],1,MM,y);
baslar.pb(yeni);
}
while(q--){
int x,y;cin>>x>>y;
cout<<cev(x,y)<<endl;
}
}
