#include <bits/stdc++.h>
using namespace std;
struct WaveletTree {
int lo, hi;
WaveletTree *L = nullptr, *R = nullptr;
vector<int> leftCnt;
WaveletTree(vector<int>::iterator l, vector<int>::iterator r, int mn, int mx)
: lo(mn), hi(mx) {
if (lo == hi || l >= r) return;
int mid = lo + (hi - lo) / 2;
leftCnt.reserve(r - l + 1);
leftCnt.push_back(0);
for (auto it = l; it != r; ++it)
leftCnt.push_back(leftCnt.back() + (*it <= mid));
auto pivot = stable_partition(l, r, [&](int x) { return x <= mid; });
L = new WaveletTree(l, pivot, lo, mid);
R = new WaveletTree(pivot, r, mid + 1, hi);
}
inline pair<int, int> mapLeft(int l, int r) const {
return {leftCnt[l - 1] + 1, leftCnt[r]};
}
inline pair<int, int> mapRight(int l, int r) const {
return {(l - 1) - leftCnt[l - 1] + 1, r - leftCnt[r]};
}
int range(int l, int r, int x, int y) const {
if (l > r || y < lo || x > hi) return 0;
if (x <= lo && hi <= y) return r - l + 1;
int res = 0;
if (L) {
auto [nl, nr] = mapLeft(l, r);
res += L->range(nl, nr, x, y);
}
if (R) {
auto [nl, nr] = mapRight(l, r);
res += R->range(nl, nr, x, y);
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<int> c(n);
for (int &x : c) cin >> x;
int mn = *min_element(c.begin(), c.end());
int mx = *max_element(c.begin(), c.end());
WaveletTree wt(c.begin(), c.end(), mn, mx);
while (q--) {
int l, r;
cin >> l >> r; // 1-based input in your example
l--, r--;
int len = r - l + 1;
int low = 0, high = len, ans = 0;
while (low <= high) {
int mid = (low + high) / 2;
// count of ≥ mid = len - count(≤ mid-1)
int cnt = len - wt.range(l + 1, r + 1, mn, mid - 1);
if (cnt >= mid) {
ans = mid;
low = mid + 1;
} else
high = mid - 1;
}
cout << ans << "\n";
}
}
