#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
int n;
vector<int> bit;
Fenwick(int n=0): n(n), bit(n+1,0) {}
void reset() { fill(bit.begin(), bit.end(), 0); }
void add(int i, int v){
for(; i<=n; i+=i&-i) bit[i]+=v;
}
int sumPrefix(int i) const{
int s=0;
for(; i>0; i-=i&-i) s+=bit[i];
return s;
}
int sumRange(int l,int r) const{
if(l>r) return 0;
return sumPrefix(r)-sumPrefix(l-1);
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,q;
cin >> n >> q;
vector<int> v(n+1);
vector<pair<int,int>> papers; papers.reserve(n);
for(int i=1;i<=n;i++){
cin >> v[i];
papers.push_back({v[i], i});
}
sort(papers.begin(), papers.end(), [&](auto &a, auto &b){
return a.first > b.first; // descending by value
});
vector<int> L(q), R(q);
for(int i=0;i<q;i++){
cin >> L[i] >> R[i];
if(L[i] > R[i]) swap(L[i], R[i]);
}
// h is in [0..len], so search on [0..len+1) => lo inclusive, hi exclusive
vector<int> lo(q, 0), hi(q);
for(int i=0;i<q;i++){
int len = R[i]-L[i]+1;
hi[i] = len + 1;
}
Fenwick fw(n);
// buckets: mid -> list of queries
vector<vector<int>> bucket(n+2);
bool changed = true;
while(changed){
changed = false;
for(int m=0;m<=n+1;m++) bucket[m].clear();
int active = 0;
for(int i=0;i<q;i++){
if(hi[i] - lo[i] > 1){
int mid = (lo[i] + hi[i]) >> 1;
bucket[mid].push_back(i);
active++;
}
}
if(active == 0) break;
fw.reset();
int pptr = 0; // pointer into papers (descending by value)
// process mids from high to low so we only sweep papers once
for(int mid=n+1; mid>=1; mid--){
// activate all positions with value >= mid
while(pptr < n && papers[pptr].first >= mid){
fw.add(papers[pptr].second, 1);
pptr++;
}
// answer all queries with this mid
for(int qi : bucket[mid]){
int cnt = fw.sumRange(L[qi], R[qi]); // #papers with citations >= mid
if(cnt >= mid) lo[qi] = mid;
else hi[qi] = mid;
changed = true;
}
}
}
for(int i=0;i<q;i++){
cout << lo[i] << "\n";
}
return 0;
}
