#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int readInt() {
int x = 0;
char ch = getchar_unlocked();
while (ch < '0' || ch > '9') ch = getchar_unlocked();
while (ch >= '0' && ch <= '9'){
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar_unlocked();
}
return x;
}
const ll MAXN = 200005, INF = 200005;
vector<int> t[4*MAXN];
void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = vector<int>(1, a[tl]);
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
merge(t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(),
back_inserter(t[v]));
}
}
int query(int v, int tl, int tr, int l, int r, int x) {
if (l > r)
return INF;
if (l == tl && r == tr) {
vector<int>::iterator pos = lower_bound(t[v].begin(), t[v].end(), x);
if (pos != t[v].end())
return *pos;
return INF;
}
int tm = (tl + tr) / 2;
return min(query(v*2, tl, tm, l, min(r, tm), x),
query(v*2+1, tm+1, tr, max(l, tm+1), r, x));
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,q;
n = readInt();
q = readInt();
int p[n+5];
for (int i=0;i<n;i++){
ll temp;
temp = readInt();
p[i] = temp;
}
build(p, 1, 0, n-1);
while (q--){
ll l,r;
l = readInt();
r = readInt();
ll range = r-l+1;
ll l2=0,r2=range+5;
while (l2<r2){
ll m = l2+(r2-l2)/2;
if(range - query(1, l-1,r-1, 0, n-1, m-1) >= m) l2=m+1;
else r2=m;
}
cout << l2-1 << "\n";
}
}
