#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
struct BIT {
int n;
vector<int> tree;
void config(int _n) {
n = _n + 10;
tree.resize(_n+60);
}
void update(int p, int v) {
for(p++; p<n; p+=p&-p) tree[p] += v;
}
int query(int p) {
int ans = 0;
for(p++; p>0; p-=p&-p) ans += tree[p];
return ans;
}
int query(int l, int r) { return query(r) - query(l-1); }
void reset() { for(int &x : tree) x = 0; }
};
stack<int> to_change[200005];
vector<int> v[200005];
int32_t main() {
ios_base::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
int n, q;
cin >> n >> q;
vector<int> L(q), R(q, 2e5), ANS(q, 1);
for(int i=1; i<=n; i++) {
int x;
cin >> x;
v[x].push_back(i);
}
vector<pii> qus(q);
for(pii &x : qus) cin >> x.first >> x.second;
bool changed = 1;
BIT bit; bit.config(2e5);
while(changed) {
changed = 0;
for(int i=0; i<q; i++)
if(L[i] <= R[i]) to_change[(L[i] + R[i]) / 2].push(i);
for(int i=2e5; i>=1; i--) {
for(int &x : v[i]) bit.update(x, 1);
while(!to_change[i].empty()) {
changed = 1;
int id = to_change[i].top();
to_change[i].pop();
if(bit.query(qus[id].first, qus[id].second) >= i) ANS[id] = i, L[id] = i + 1;
else R[id] = i - 1;
}
}
bit.reset();
}
for(int &x : ANS) cout << x << '\n';
return 0;
}
