#include <bits/stdc++.h>
// #define int long long
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define kill(x) cout << x << "\n", exit(0);
#define pii pair<int, int>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
const int MAXN = (int)2e5 + 7;
const int MOD = 998244353;
const int INF = (int)1e9 + 7;
int n, m, k, tmp, t, tmp2, tmp3, tmp4, u, v, w, flag, q, ans, flag2;
int arr[MAXN], h[MAXN], res[MAXN];
vector<int> vec[MAXN];
/* Presistent SegTree */
#define mid ((l+r)>>1)
struct Node {
int val; Node *l, *r;
Node(int x) {
val = x; l = r = NULL;
}
Node(Node *ll, Node *rr) {
l = ll; r = rr;
if (l) val += l->val;
if (r) val += r->val;
}
Node(Node *node) {
val = node->val; l = node->l; r = node->r;
}
};
Node *build(int l=0, int r=n) {
if (l+1 == r) return new Node(0);
return new Node(build(l, mid), build(mid, r));
}
Node *upd(Node *node, int ind, int l=0, int r=n) {
if (l+1 == r) return new Node((node->val)+1);
if (ind < mid) return new Node(upd(node->l, ind, l, mid), node->r);
return new Node(node->l, upd(node->r, ind, mid, r));
}
int get(Node *node, int s, int t, int l=0, int r=n) {
if (s >= t) return 0;
if (s <= l && t >= r) return node->val;
if (t <= mid) return get(node->l, s, t, l, mid);
if (s >= mid) return get(node->r, s, t, mid, r);
return get(node->l, s, t, l, mid)+get(node->r, s, t, mid, r);
}
/* Presistent SegTree */
Node *seg[MAXN];
int32_t main() {
#ifdef LOCAL
freopen("inp.in", "r", stdin);
freopen("res.out", "w", stdout);
#else
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
cin >> n >> q;
for (int i=1; i<=n; i++) {
cin >> arr[i];
vec[arr[i]].pb(i);
}
seg[0] = build();
for (int i=1; i<MAXN; i++) {
seg[i] = new Node(seg[i-1]);
for (int u:vec[i]) seg[i] = upd(seg[i], u-1);
}
while (q--) {
cin >> u >> v;
int l = 1, r = v-u+2;
while (r-l > 1) {
if (v-u+1-get(seg[mid-1], u-1, v) >= mid) l = mid;
else r = mid;
}
cout << l << endl;
}
return 0;
}
