#include <bits/stdc++.h>
using namespace std;
const int BLOCK_SIZE = 320;
struct FenwickTree{
vector<int> tree;
void init(int n){
tree.assign(n + 2, 0);
}
void update(int v, int val) {
for (; v < tree.size(); v += v & (-v)){
tree[v]+= val;
}
}
int get(int v) {
int res = 0;
for (; v; v -= v & (-v)){
res += tree[v];
}
return res;
}
} bit;
bool cmp(array<int, 3> a, array<int, 3> b) {
if (a[0] / BLOCK_SIZE == b[0] / BLOCK_SIZE) return a[1] < b[1];
return a[0] / BLOCK_SIZE < b[0] / BLOCK_SIZE;
}
void solve(){
int n, q; cin >> n >> q;
vector<int> p(n + 1), ans(q + 1);
vector<array<int, 3>> qry(q + 1);
for(int i = 1; i <= n; i++) cin >> p[i];
for(int i = 1; i <= q; i++){
int l, r; cin >> l >> r;
qry[i] = {l, r, i};
}
sort(qry.begin() + 1, qry.end(), cmp);
bit.init(2000005);
int curl = 1, curr = 0;
for(int i = 1; i <= q; i++) {
int l = qry[i][0], r = qry[i][1];
while(curl > l){
curl--;
bit.update(p[curl], 1);
}
while(curl < l) {
bit.update(p[curl], -1);
curl++;
}
while(curr < r){
curr++;
bit.update(p[curr], 1);
}
while(curr > r) {
bit.update(p[curr], -1);
curr--;
}
int low = 1, high = 2000000, res = 1;
while(low <= high) {
int mid = (low + high) / 2;
if(bit.get(2000000) - bit.get(mid - 1) >= mid){
low = mid + 1;
res = mid;
} else high = mid - 1;
}
ans[qry[i][2]] = res;
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
solve();
return 0;
}
