#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
struct node{
int s, e, m, val;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, val = 0;
if (s != e){
l = new node(s, m); r = new node(m + 1, e);
}
}
node (node *x){
s = x->s, e = x->e, m = x->m, val = x->val, l = x->l, r = x->r;
}
void update(int x, int v){
if (s == e){
val += v; return;
}
if (x <= m){
l = new node(l); l->update(x, v);
}
else{
r = new node(r); r->update(x, v);
}
val = l->val + r->val;
}
int query(int x, int y){
if (x == s && y == e) return val;
else if (y <= m) return l->query(x, y);
else if (x > m) return r->query(x, y);
else return l->query(x, m) + r->query(m + 1, y);
}
};
node *root[MAXN];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int nums, queries; cin >> nums >> queries;
vector<vector<int>> vec(nums + 1);
for (int i = 1; i <= nums; i++){
int x; cin >> x; x = min(x, nums);
vec[x].push_back(i);
}
root[0] = new node(1, nums);
for (int x = 1; x <= nums; x++){
root[x] = new node(root[x - 1]);
for (int i : vec[x]) root[x]->update(i, 1);
}
while (queries--){
int l, r, sz; cin >> l >> r; sz = r - l + 1;
int lo = 1, hi = sz, ans;
while (lo <= hi){
int m = (lo + hi) >> 1;
if (sz - root[m - 1]->query(l, r) >= m){
ans = m; lo = m + 1;
}
else hi = m - 1;
}
cout << ans << '\n';
}
}
