#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define INF (int)(1e9)
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct Query{
int x, y, l, r, i;
};
const int N = 2e5 + 69;
int a[N];
vector <Query> adj[N];
int n, q;
int ans[N];
int seg[4 * N];
vector <Query> all;
vector <int> vec[N];
void upd(int l, int r, int pos, int qp){
seg[pos]++;
if (l == r){
return;
}
int mid = (l + r)/2;
if (qp <= mid) upd(l, mid, pos*2, qp);
else upd(mid + 1, r, pos*2 + 1, qp);
seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
int query(int l, int r, int pos, int ql, int qr){
if (l >= ql && r <= qr) return seg[pos];
else if (l > qr || r < ql) return 0;
int mid = (l + r)/2;
return query(l, mid, pos*2, ql, qr) + query(mid + 1, r, pos*2 + 1, ql, qr);
}
void pbs(){
all.clear();
for (int i = 0; i <= n; i++){
for (auto x : adj[i]){
all.push_back(x);
}
adj[i].clear();
}
for (auto x : all){
adj[(x.l + x.r + 1)/2].push_back(x);
}
for (int i = 0; i < 4 * n; i++){
seg[i] = 0;
}
for (int i = n; i >= 0; i--){
for (auto x : vec[i]){
upd(1, n, 1, x);
}
for (auto &x : adj[i]){
if (x.l == x.r) continue;
int val = query(1, n, 1, x.x, x.y);
//cout << x.x << " " << x.y << " " << val << " " << i << "\n";
if (val >= i){
x.l = i;
} else {
x.r = i - 1;
}
}
}
}
void Solve(){
cin >> n >> q;
for (int i = 1; i <= n; i++){
cin >> a[i];
vec[a[i]].push_back(i);
}
for (int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
Query ok;
ok.x = l;
ok.y = r;
ok.l = 0;
ok.r = n;
ok.i = i;
adj[0].push_back(ok);
}
for (int it = 0; it < 20; it++){
pbs();
}
for (int i = 0; i <= n; i++){
for (auto x : adj[i]){
ans[x.i] = x.l;
}
}
for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
//cin >> t;
while (t--) Solve();
return 0;
}
