#include <bits/stdc++.h>
using namespace std;
struct node {
int val;
node *L, *R;
node(int val) : val(val),L(NULL),R(NULL) {}
node(node *l, node *r) : val(0), L(l), R(r) {
if (l) val+=l->val;
if (r) val+=r->val;
}
};
node* build(int l, int r) {
if (l==r) return new node(0);
else {
int mid=(l+r)/2;
return new node(build(l,mid),build(mid+1,r));
}
}
node* update(node *v, int l, int r, int x, int val) {
if (x>r || x<l) return v;
if (l==r) return new node(v->val+val);
int mid=(l+r)/2;
return new node(update(v->L,l,mid,x,val),update(v->R,mid+1,r,x,val));
}
int query(node *v, int l, int r, int x, int y) {
if (x>r || y<l) return 0;
if (x<=l && r<=y) return v->val;
int mid=(l+r)/2;
return query(v->L,l,mid,x,y)+query(v->R,mid+1,r,x,y);
}
vector<node*> arr;
int n,q;
const int mx=200005;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin>>n>>q;
arr.push_back(build(1,mx));
for (int i=1; i<=n; ++i) {
int x; cin>>x;
arr.push_back(update(update(arr.back(),1,mx,1,1),1,mx,x+1,-1));
}
while (q--) {
int a,b; cin>>a>>b;
int l=1,r=mx;
while (l<r) {
int mid=(l+r+1)/2;
if (query(arr[b],1,mx,1,mid)-query(arr[a-1],1,mx,1,mid)>=mid) l=mid;
else r=mid-1;
}
cout<<l<<"\n";
}
}
