#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;
#define pb push_back
#define ins insert
#define fi first
#define se second
// #define endl "\n"
#define ALL(x) x.begin(), x.end()
#define intt long long
const intt mod = 1e9 + 7;
const intt base = 9973;
const intt inf = 1e18;
const intt mxN = 5e5 + 5;
const intt L = 21;
struct query {
intt l, r, i;
};
intt bsz = 500;
bool cmp(query &a, query &b) {
if(a.l / bsz == b.l / bsz) {
return a.r > b.r;
}
return a.l / bsz < b.l / bsz;
}
vector<intt> Bit(mxN), A(mxN);
void upd(intt x, intt delta) {
while(x <= mxN) {
Bit[x] += delta;
Bit[x] = max(0ll, Bit[x]);
x += x & -x;
}
}
intt qry(intt x, intt k, intt ql, intt qr) {
intt cnt = 0;
while(x > 0) {
// if(ql == 0 && qr == 6) {
// cout << cnt << " " << k << " " << Bit[x] << " " << x << endl;
// }
cnt += Bit[x];
x -= x & -x;
}
return cnt;
}
void rem(intt x) {
upd(x, -1);
}
void add(intt x) {
upd(x, 1ll);
}
void solve() {
intt N, Q;
cin >> N >> Q;
for(intt i = 0; i < N; i++) {
cin >> A[i];
}
vector<query>qrys;
vector<intt> ans(Q);
for(intt i = 0; i < Q; i++) {
intt l, r;
cin >> l >> r;
--l;--r;
qrys.pb({l,r,i});
}
sort(ALL(qrys), cmp);
intt curl = 0, curr = -1;
for(intt i = 0; i < Q; i++) {
intt l = qrys[i].l, r = qrys[i].r, idx = qrys[i].i;
while(curl > l) {
curl--; add(A[curl]);
// cout << "1" << endl;
}
while(curl < l) {
rem(A[curl]); curl++;
// cout << "11" << endl;
}
while(curr < r) {
curr++;
add(A[curr]);
// cout << "111" << endl;
}
while(curr > r) {
rem(A[curr]);
curr--;
// cout << "1111" << endl;
}
intt bl = 1, br = 200001, anss = 0;
while(bl <= br) {
intt mid = (bl + br) / 2;
// if(l == 0 && r == 6) {
// cout << mid << ": " << qry(mxN, mid, l, r) << endl;
// }
if(qry(mxN, mid, l, r) - qry(mid-1, mid, l, r) >= mid) {
bl = mid + 1;
anss = mid;
} else {
br = mid - 1;
}
}
ans[idx] = anss;
}
for(intt i = 0; i < Q; i++) {
cout << ans[i] << " ";
}
cout << endl;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
intt tst = 1;
// cin >> tst;
while(tst--) {
solve();
}
}
