#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using ll = long long;
#define int ll
#define sz(x) (int)x.size()
const int N = 2e5+5;
int n, q;
int p[N];
vector<int> T[2*N];
void init(int i, int tl, int tr){
if(tl == tr){
T[i].push_back(p[tl]);
return;
}
int m = (tl + tr) / 2;
init(2*i+1, tl, m);
init(2*i+2, m+1, tr);
merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));
}
int query(int l, int r, int k, int i, int tl, int tr){
if(r < tl or l > tr){
return 0;
}
if(l <= tl && tr <= r){
return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
}
int m = (tl + tr) / 2;
return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}
int query(int l, int r, int k){
return query(l, r, k, 0, 0, n-1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i=0; i<n; ++i){
cin >> p[i];
}
init(0, 0, n-1);
while(q--){
int l, r;
cin >> l >> r;
l--, r--;
int low = 1, high = r - l + 1;
int res = 1;
while(low <= high){
int mid = (low + high) / 2;
int tmp = r - l + 1 - query(l, r, mid);
if(tmp >= mid){
res = mid;
low = mid+1;
} else {
high = mid-1;
}
}
cout << res << endl;
}
}
