/*
ID: gabriel139
LANG: C++
TASK: test
*/
/* clang-format off */
#include <bits/stdc++.h>
using namespace std;
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
err(++it, args...);
}
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define dbg(x) cout << #x << " = " << x << endl
#define printv(a) {for(auto u:a) cout<<u<<" "; cout<<endl;}
#define all(x) x.begin(), x.end()
#define int long long
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define lb(vect, x) (lower_bound(all(vect), x) - vect.begin())
#define ub(vect, x) (upper_bound(all(vect), x) - vect.begin())
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
void NO() { cout << "NO" << endl; }
void YES() { cout << "YES" << endl; }
bool prime(ll a) { if (a <= 1) return 0; if (a == 2) return 1; if (a % 2 == 0) return 0; for (int i = 3; i*i <= a; i+=2) if (a % i == 0) return 0; return 1; }
const int MOD = 1e9 + 7, MAX = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
/* clang-format on */
struct Vertex
{
Vertex *l, *r;
int sum;
Vertex(int val) : l(nullptr), r(nullptr), sum(val) {}
Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0)
{
if (l) sum += l->sum;
if (r) sum += r->sum;
}
};
Vertex *build(int tl, int tr)
{
if (tl == tr) return new Vertex(0);
int tm = (tl + tr) / 2;
return new Vertex(build(tl, tm), build(tm + 1, tr));
}
Vertex *update(Vertex *v, int tl, int tr, int pos)
{
if (tl == tr) return new Vertex(v->sum + 1);
int tm = (tl + tr) / 2;
if (pos <= tm) return new Vertex(update(v->l, tl, tm, pos), v->r);
else return new Vertex(v->l, update(v->r, tm + 1, tr, pos));
}
int find_kth(Vertex *vl, Vertex *vr, int tl, int tr, int k)
{
if (tl == tr) return tl;
int tm = (tl + tr) / 2, left_count = vr->l->sum - vl->l->sum;
if (left_count >= k) return find_kth(vl->l, vr->l, tl, tm, k);
return find_kth(vl->r, vr->r, tm + 1, tr, k - left_count);
}
vector<Vertex *> st(MAX);
vi arr(MAX);
void solve()
{
int n, q;
cin >> n >> q;
st[0] = build(1, n);
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
arr[i] = (arr[i] > n) ? n : arr[i];
st[i] = update(st[i - 1], 1, n, arr[i]);
}
for (int i = 0; i < q; i++)
{
int l, r;
cin >> l >> r;
int len = r - l + 1;
int low = 1, high = len, ans = 0;
while (low <= high)
{
int mid = low + (high - low) / 2;
// Como implementamos a busca do k-ésimo menor, convertemos
// para k-ésimo maior fazendo n - k + 1
int kesimo = len - mid + 1;
int val = find_kth(st[l - 1], st[r], 1, n, kesimo);
if (val >= mid)
{
ans = mid;
low = mid + 1;
continue;
}
high = mid - 1;
}
cout << ans << "\n";
}
}
int32_t main()
{
// freopen("test.in", "r", stdin);
// freopen("test.out", "w", stdout);
// casas decimais
// cout << fixed << setprecision(1);
// horario
// cout << setfill('0') << setw(2);
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
for (int i = 1; i <= t; i++)
{
solve();
// #ifdef ONPC
// cout << "__________________________" << endl;
// #endif
}
return 0;
}
