#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC target("popcnt")
#pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,tune=native")
#pragma GCC optimize(3)
#pragma GCC optimize("O3")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
using namespace std;
using ld = long double;
using ll = long long;
#define int ll
#define sz(x) (int)x.size()
const int N = 2e5+5;
int n, q;
int p[N];
vector<int> T[4*N];
void init(int i, int tl, int tr){
if(tl == tr){
T[i].push_back(p[tl]);
return;
}
int m = (tl + tr) / 2;
init(2*i+1, tl, m);
init(2*i+2, m+1, tr);
merge(T[2*i+1].begin(), T[2*i+1].end(), T[2*i+2].begin(), T[2*i+2].end(), back_inserter(T[i]));
}
int query(int l, int r, int k, int i, int tl, int tr){
if(r < tl or l > tr){
return 0;
}
if(l <= tl && tr <= r){
return lower_bound(T[i].begin(), T[i].end(), k) - T[i].begin();
}
int m = (tl + tr) / 2;
return query(l, r, k, 2*i+1, tl, m) + query(l, r, k, 2*i+2, m+1, tr);
}
int query(int l, int r, int k){
return query(l, r, k, 0, 0, n-1);
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> q;
for(int i=0; i<n; ++i){
cin >> p[i];
}
init(0, 0, n-1);
while(q--){
int l, r;
cin >> l >> r;
l--, r--;
int low = 1, high = r - l + 1;
int res = 1;
while(low <= high){
int mid = (low + high) / 2;
int tmp = r - l + 1 - query(l, r, mid);
if(tmp >= mid){
res = mid;
low = mid+1;
} else {
high = mid-1;
}
}
cout << res << endl;
}
}
