#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using vi = vector<int>;
struct segtree
{
int l;
int r;
int v = 0;
segtree* left = NULL;
segtree* right = NULL;
segtree()
{
;
}
segtree(int L, int R)
{
l = L;
r = R;
if(l == r) return;
int m = (l+r)/2;
left = new segtree(l, m);
right = new segtree(m+1, r);
}
segtree(int L, int R, int V, segtree* LEFT, segtree* RIGHT)
{
l = L, r = R, v = V, left = LEFT, right = RIGHT;
}
int rangesum(int L, int R)
{
if(R < l || r < L) return 0;
else if(L <= l && r <= R) return v;
else return left->rangesum(L, R) + right->rangesum(L, R);
}
segtree* add(int I, int V)
{
if(I < l || r < I) return this;
else if(l == r) return new segtree{l, r, v+V, NULL, NULL};
else
{
segtree* new_left = left->add(I, V);
segtree* new_right = right->add(I, V);
return new segtree(l, r, v+V, new_left, new_right);
}
}
};
const int mx = 200'000;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q;
cin >> n >> q;
segtree* S[1+mx+1];
S[mx+1] = new segtree(1, n);
vi p(1+n);
vi occ[1+mx];
for(int i = 1; i <= n; i++)
{
cin >> p[i];
occ[p[i]].push_back(i);
}
for(int v = mx; v >= 0; v--)
{
S[v] = S[v+1];
for(int i : occ[v])
S[v] = S[v]->add(i, 1);
}
for(int j = 1; j <= q; j++)
{
int l, r;
cin >> l >> r;
int lo = 0;
int hi = mx;
while(lo != hi)
{
int mid = (lo+hi)/2 + 1;
if(S[mid]->rangesum(l, r) >= mid)
lo = mid;
else
hi = mid-1;
}
cout << lo << '\n';
}
}
