#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define name "a"
using namespace std;
using ii = pair<int,int>;
using aa = array<int,4>;
const int N=2e5+5;
const int MOD=1e9+7;
struct PSMT {
int S[N*25],L[N*25],R[N*25];
int timer=0;
vector<int> root;
int create(int val,int l,int r) {
S[++timer]=val;
L[timer]=l;
R[timer]=r;
return timer;
}
int build(int l,int r) {
if(l==r) {
return create(0,0,0);
}
int mid = l + r >> 1;
return create(0,build(l,mid),build(mid+1,r));
}
void setup() {
root.push_back(0);
build(1,N-5);
}
int upd(int id,int l,int r,int pos,int val) {
if(pos < l || r < pos) return id;
if(l==r) {
return create(S[id]+val,0,0);
}
int mid = l + r >> 1;
int left=upd(L[id],l,mid,pos,val);
int right=upd(R[id],mid+1,r,pos,val);
return create(S[left]+S[right],left,right);
}
int GET(int id,int l,int r,int u,int v){
if(v < l || r < u) return 0;
if(u<=l && r<=v) {
return S[id];
}
int mid = l + r >> 1;
int left=GET(L[id],l,mid,u,v);
int right=GET(R[id],mid+1,r,u,v);
return left+right;
}
void update(int pos,int val) {
root.push_back(upd(root.back(),1,N-5,pos,val));
}
int get(int u,int l,int r) {
return GET(root[u],1,N-5,l,r);
}
} SMT;
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int n,q;
cin >> n >> q;
SMT.setup();
for(int i=1;i<=n;i++) {
int x;
cin >> x;
SMT.update(x,1);
}
while(q--) {
int x,y;
cin >> x >> y;
int l=1,r=n;
int ans=0;
while(l<=r) {
int mid = l + r >> 1;
if(SMT.get(y,mid,n)-SMT.get(x-1,mid,n)>=mid) {
l=mid+1;
ans=mid;
}
else {
r=mid-1;
}
}
cout << ans << endl;
}
return 0;
}
