#include <bits/stdc++.h>
using namespace std;
typedef tuple<int, int, int> i3;
const int MAXN = 200005;
int fw[MAXN], ans[MAXN];
vector<int> vec[MAXN];
int nums, queries;
void update(int x, int v){
while (x <= nums){
fw[x] += v;
x += (x & (-x));
}
}
int query(int x){
int ans = 0;
while (x){
ans += fw[x];
x -= (x & (-x));
}
return ans;
}
void dnc(int lo, int hi, int pm, vector<i3> &qv){
if (lo > hi) return;
int m = (lo + hi) >> 1;
for (int x = pm; x < m; x++){
for (int i : vec[x])
update(i, 1);
}
vector<i3> lqv, rqv;
for (auto &[l, r, id] : qv){
if (r - l + 1 - (query(r) - query(l - 1)) >= m){
ans[id] = m;
rqv.push_back({l, r, id});
}
else lqv.push_back({l, r, id});
}
dnc(m + 1, hi, m, rqv);
for (int x = pm; x < m; x++){
for (int i : vec[x])
update(i, -1);
}
dnc(lo, m - 1, pm, lqv);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> nums >> queries;
for (int i = 1; i <= nums; i++){
int x; cin >> x; x = min(x, nums);
vec[x].push_back(i);
}
vector<i3> qv(queries);
for (int i = 0; i < queries; i++){
int l, r; cin >> l >> r;
qv[i] = {l, r, i};
}
dnc(1, nums, 1, qv);
for (int i = 0; i < queries; i++) cout << ans[i] << '\n';
}
