#include <bits/stdc++.h>
using namespace std;
long long i, j, l, r, mid, p, q, k, t, n, m, a, b, c, d, ans, cnt, res, kmy[200005], kmy4[200005], st[800005];
pair <long long, long long> kmy2[200005];
struct aa{
long long id;
long long ll;
long long rr;
long long qa;
long long qb;
long long qc;
};
aa query[200005];
vector <aa> kmy3[200005];
const long long mod = 999993143;
string s;
bool check;
void build (long long id, long long l, long long r){
if (l == r){
st[id] = kmy4[l];
return;
}
long long mid = (l + r) >> 1;
build(id * 2, l, mid);
build(id * 2 + 1, mid + 1, r);
st[id] = st[id * 2] + st[id * 2 + 1];
}
void update (long long id, long long l, long long r, long long i, long long val){
if (i < l || i > r){
return;
}
if (l == r){
st[id] += val;
return;
}
long long mid = (l + r) >> 1;
update(id * 2, l, mid, i, val);
update(id * 2 + 1, mid + 1, r, i, val);
st[id] = st[id * 2] + st[id * 2 + 1];
}
long long get (long long id, long long l, long long r, long long u, long long v){
if (v < l || u > r){
return 0;
}
if (u <= l && r <= v){
return st[id];
}
long long mid = (l + r) >> 1;
return get(id * 2, l, mid, u, v) + get(id * 2 + 1, mid + 1, r, u, v);
}
bool cmp (pair <long long, long long> a, pair <long long, long long> b){
return a.first > b.first;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for (i = 1; i <= n; i += 1){
cin >> kmy[i];
kmy4[i] = 0;
}
for (i = 1; i <= q; i += 1){
cin >> a >> b;
query[i] = {i, 1, n, a, b, -1};
}
for (i = 1; i <= n; i += 1){
kmy2[i] = make_pair(kmy[i], i);
}
sort(kmy2 + 1, kmy2 + n + 1, cmp);
for (d = 1; d <= 18; d += 1){
build(1, 1, n);
for (i = 1; i <= n; i += 1){
kmy3[i].clear();
}
for (i = 1; i <= q; i += 1){
kmy3[(query[i].ll + query[i].rr) >> 1ll].push_back(query[i]);
}
p = 1;
for (i = n; i >= 1; i -= 1){
while (p <= n){
// cout << p << "a\n";
if (kmy2[p].first >= i){
update(1, 1, n, kmy2[p].second, 1);
p += 1;
}
else{
break;
}
}
for (j = 0; j < kmy3[i].size(); j += 1){
if (query[kmy3[i][j].id].ll > query[kmy3[i][j].id].rr){
continue;
}
if (get(1, 1, n, query[kmy3[i][j].id].qa, query[kmy3[i][j].id].qb) >= i){
query[kmy3[i][j].id].qc = max(query[kmy3[i][j].id].qc, i);
query[kmy3[i][j].id].ll = i + 1;
}
else{
query[kmy3[i][j].id].rr = i - 1;
}
}
}
}
for (i = 1; i <= q; i += 1){
if (query[i].qa == query[i].qb){
cout << 1 << "\n";
}
else{
cout << query[i].qc << "\n";
}
}
}
