#include <stdio.h>
#define N 200000
#define LN 18 /* LN = ceil(log2(N)) */
#define N_ (1 + N * (LN + 1))
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int aa[N];
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k) {
int c = aa[ii[j]] - aa[i_];
if (c == 0)
j++;
else if (c < 0) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
}
sort(ii, l, i);
l = k;
}
}
int ll[N_], rr[N_], kk[N_], _;
int update(int t, int l, int r, int i) {
int t_ = ++_;
kk[t_] = kk[t] + 1;
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll[t_] = update(ll[t], l, m, i), rr[t_] = rr[t];
else
ll[t_] = ll[t], rr[t_] = update(rr[t], m, r, i);
}
return t_;
}
int query(int t, int l, int r, int ql, int qr) {
int m;
if (qr <= l || r <= ql || t == 0)
return 0;
if (ql <= l && r <= qr)
return kk[t];
m = (l + r) / 2;
return query(ll[t], l, m, ql, qr) + query(rr[t], m, r, ql, qr);
}
int main() {
static int ii[N], tt[N + 1];
int n, q, i, a, t;
scanf("%d%d", &n, &q);
for (i = 0; i < n; i++) {
scanf("%d", &aa[i]);
ii[i] = i;
}
sort(ii, 0, n);
for (a = n, i = n - 1, t = 0; a >= 0; a--) {
while (i >= 0 && aa[ii[i]] >= a)
t = update(t, 0, n, ii[i--]);
tt[a] = t;
}
while (q--) {
int l, r, lower, upper;
scanf("%d%d", &l, &r), l--;
lower = 1, upper = r - l + 1;
while (upper - lower > 1) {
int a = (lower + upper) / 2;
if (query(tt[a], 0, n, l, r) >= a)
lower = a;
else
upper = a;
}
printf("%d\n", lower);
}
return 0;
}
