#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX = 2000005;
// Constructs a segment tree and stores sTree[]
void buildTree(int idx, int ss, int se, vector<ll> a[],
vector<ll> sTree[])
{
/*leaf node*/
if (ss == se) {
sTree[idx] = a[ss];
return;
}
int mid = (ss + se) / 2;
/* building left subtree */
buildTree(2 * idx + 1, ss, mid, a, sTree);
/* building right subtree */
buildTree(2 * idx + 2, mid + 1, se, a, sTree);
/* merging left and right child in sorted order */
merge(sTree[2 * idx + 1].begin(),
sTree[2 * idx + 1].end(),
sTree[2 * idx + 2].begin(),
sTree[2 * idx + 2].end(),
back_inserter(sTree[idx]));
}
// Recursive function to count smaller elements from row
// a[ss] to a[se] and value smaller than or equal to k.
int queryRec(int node, int start, int end, int ss, int se,
int k, vector<ll> a[], vector<ll> sTree[])
{
/* If out of range return 0 */
if (ss > end || start > se)
return 0;
/* if inside the range return count */
if (ss <= start && se >= end) {
/* binary search over the sorted vector
to return count >= X */
return upper_bound(sTree[node].begin(),
sTree[node].end(), k)
- sTree[node].begin();
}
int mid = (start + end) / 2;
/*searching in left subtree*/
int p1 = queryRec(2 * node + 1, start, mid, ss, se, k,
a, sTree);
/*searching in right subtree*/
int p2 = queryRec(2 * node + 2, mid + 1, end, ss, se, k,
a, sTree);
/*adding both the result*/
return p1 + p2;
}
// A wrapper over query().
int query(int start, int end, int k, vector<ll> a[], int n,
vector<ll> sTree[])
{
return queryRec(0, 0, n - 1, start, end, k, a, sTree);
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,q;
cin >> n >> q;
vector<ll> p[n+5];
for (int i=0;i<n;i++){
ll temp;
cin >> temp;
p[i].push_back(temp);
}
vector<ll> sTree[MAX];
buildTree(0,0,n-1,p,sTree);
while (q--){
ll l,r;
cin >> l >> r;
ll l2=0,r2=200005,m;
while (l2<r2){
m = l2+(r2-l2)/2;
ll range = r-l+1;
if(range - query(l-1,r-1,m-1,p,n,sTree) >= m) l2=m+1;
else r2=m;
}
cout << l2-1 << "\n";
}
}
