#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1<<18;
vector<int> Mid[N];
vector<pair<int, int>> vec;
int ft[N], l[N], r[N], L[N], R[N];
void Add(int i, int v){
for (; i < N; i += i & -i)
ft[i]++;
}
int get(int i, int ans = 0){
for (; i; i -= i & -i)
ans += ft[i];
return ans;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q;
cin>>n>>q;
for (int i=1, a;i<=n;i++){
cin>>a;
vec.push_back({min(a, n), i});
}
sort(begin(vec), end(vec));
for (int i=1;i<=q;i++){
cin>>l[i]>>r[i];
L[i] = 1, R[i] = n+1;
Mid[(n + 2) / 2].push_back(i);
}
for (int j=1;j<=20;j++){
for (int i=n, s = vec.size()-1;i>=1;i--){
while (s >= 0 and vec[s].first == i)
Add(vec[s--].second, 1);
for (int k : Mid[i]){
if (get(r[k]) - get(l[k]-1) >= i)
L[k] = i;
else
R[k] = i;
}
Mid[i].clear();
}
for (int i=1;i<N;i++){
ft[i] = 0;
if (i <= q and L[i] + 1 < R[i])
Mid[(L[i] + R[i]) / 2].push_back(i);
}
}
for (int i=1;i<=q;i++)
cout<<L[i]<<'\n';
}
