#include <bits/stdc++.h>
using namespace std;
int ft[400005], X;
int qry(int idx) {
int ans = 0;
for (; idx > 0; idx -= idx&(-idx)) ans += ft[idx];
return ans;
}
void add(int idx, int v) {
for(; idx <= X; idx += (idx&-idx)) ft[idx] += v;
}
const int N = 500;
bool comp(pair<pair<int, int>,int> x, pair<pair<int, int>,int> y) {
return make_pair(x.first.first/N, x.first.second) < make_pair(y.first.first/N, y.first.second);
}
int main() {
X = 200001;
int n; cin >> n;
int q; cin >> q;
int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
int ans[q];
vector<pair<pair<int, int>, int>> queries(q);
for (int i = 0; i < q; i++) {
int s, e; cin >> s >> e;
s--;e--;
queries[i] = {{s, e}, i};
}
sort(queries.begin(), queries.end(), comp);
int curL = 0;
int curR = -1;
multiset<int> s;
for (auto x:queries) {
while (curL < x.first.first) {
add(a[curL], -1);
curL++;
}
while (curL > x.first.first) {
curL--;
add(a[curL], 1);
}
while (curR < x.first.second) {
curR++;
add(a[curR], 1);
}
while (curR > x.first.second) {
add(a[curR], -1);
curR--;
}
int l = 0;
int r = 200005;
while (r-l > 1) {
int mid = (r+l)/2;
if (x.first.second-x.first.first+1-qry(mid-1) >= mid) l = mid;
else r = mid;
}
ans[x.second] = l;
}
for (int i = 0; i < q; i++) cout << ans[i] << '\n';
}
