#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
struct Node{
int sum;
Node *leftChild, *rightChild;
Node(int _x){
sum = _x;
leftChild = rightChild = nullptr;
}
};
Node* Build(int l, int r){
Node *res = new Node(0);
if (l == r)
return res;
int mid = (l + r) >> 1;
res->leftChild = Build(l, mid);
res->rightChild = Build(mid + 1, r);
res->sum = res->leftChild->sum + res->rightChild->sum;
return res;
}
Node* Update(Node *cur, int l, int r, int pos){
if (pos < l || r < pos)
return cur;
Node *res = new Node(1);
if (l == r)
return res;
int mid = (l + r) >> 1;
res->leftChild = Update(cur->leftChild, l, mid, pos);
res->rightChild = Update(cur->rightChild, mid + 1, r, pos);
res->sum = res->leftChild->sum + res->rightChild->sum;
return res;
}
int Get(Node *cur, int l, int r, int u, int v){
if (v < l || r < u)
return 0;
if (u <= l && r <= v)
return cur->sum;
int mid = (l + r) >> 1;
return Get(cur->leftChild, l, mid, u, v) + Get(cur->rightChild, mid + 1, r, u, v);
}
int n, q, p[N], ind[N];
Node *ver[N], *root;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
for(int i = 1; i <= n; i++){
cin >> p[i];
ind[i] = i;
}
root = Build(1, n);
sort(ind + 1, ind + 1 + n, [&](const int &x, const int &y){
return p[x] > p[y];
});
int ptr = 1;
for(int i = n; i >= 1; i--){
while (ptr <= n && p[ind[ptr]] >= i)
root = Update(root, 1, n, ind[ptr++]);
ver[i] = root;
}
while (q--){
int l, r, lo = 2, hi = n, res = 1;
cin >> l >> r;
while (lo <= hi){
int mid = (lo + hi) >> 1;
if (Get(ver[mid], 1, n, l, r) >= mid){
res = mid;
lo = mid + 1;
} else {
hi = mid - 1;
}
}
cout << res << '\n';
}
return 0;
}
