#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define SZ(x) ((int) (x).size())
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define debug(x) cerr << "[" << #x << " = " << (x) << "]" << endl
#define left __left
#define right __right
#define prev __prev
#define fi first
#define se second
template <class X, class Y>
bool maximize(X &x, Y y) {
if (x < y) return x = y, true;
else return false;
}
template <class X, class Y>
bool minimize(X &x, Y y) {
if (x > y) return x = y, true;
else return false;
}
int n, q;
#define MAX_N 200'200
int a[MAX_N + 2];
struct MST {
vector <int> seg[4 * MAX_N + 2];
vector <int> Merge(const vector <int> &a, const vector <int> &b) {
vector <int> res;
int i = 0, j = 0;
while (i < SZ(a) && j < SZ(b)) {
if (a[i] <= b[j]) {
res.push_back(a[i++]);
} else {
res.push_back(b[j++]);
}
}
while (i < SZ(a)) res.push_back(a[i++]);
while (j < SZ(b)) res.push_back(b[j++]);
return res;
}
void build(int id, int l, int r) {
if (l == r) {
seg[id].push_back(a[l]);
return;
}
int g = (l + r) >> 1;
build(id << 1, l, g);
build(id << 1 | 1, g + 1, r);
seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
}
int get(int id, int l, int r, int u, int v, const int &value) {
if (l > v || u > r) return 0;
if (u <= l && r <= v) {
int lef = 0, rig = SZ(seg[id]) - 1, g, vt = -1;
while (lef <= rig) {
g = (lef + rig) >> 1;
if (seg[id][g] >= value) vt = g, rig = g - 1;
else lef = g + 1;
}
if (vt == -1) return 0;
return SZ(seg[id]) - vt;
}
int g = (l + r) >> 1;
return get(id << 1, l, g, u, v, value) + get(id << 1 | 1, g + 1, r, u, v, value);
}
} st;
int main() {
ios_base::sync_with_stdio(false);cin.tie(nullptr);
// freopen("test.inp","r",stdin);
// freopen("test.out","w",stdout);
cin >> n >> q;
FOR(i, 1, n) cin >> a[i];
st.build(1, 1, n);
while (q--) {
int L, R;
cin >> L >> R;
int l = 1, r = R - L + 1, g, vt = -1;
while (l <= r) {
g = (l + r) >> 1;
if (st.get(1, 1, n, L, R, g) >= g) vt = g, l = g + 1;
else r = g - 1;
}
if (vt == -1) vt = 0;
cout << vt << "\n";
}
return 0;
}
/* Discipline - Calm */
