#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const int MAXN = 2e5+5, SEG = MAXN*22, MAXP = 2e5;
int N, Q, X, Y, cnt, val[SEG], lef[SEG], rig[SEG], ver[MAXN];
vector <int> P[MAXN];
int build(int L,int R) {
int x = cnt;
cnt++;
if (L == R) {
val[x] = 0;
}
else {
int mid=(L+R)/2;
lef[x] = build(L,mid);
rig[x] = build(mid+1,R);
val[x] = val[lef[x]] + val[rig[x]];
}
return x;
}
int query(int tr,int x,int y,int L,int R) {
if (x <= L && y >= R) {
return val[tr];
}
if (x > R || y < L) {
return 0;
}
int mid = (L+R)/2;
return query(lef[tr],x,y,L,mid) + query(rig[tr],x,y,mid+1,R);
}
int update(int tr,int x,int y,int L,int R) { // arr[x] = y;
int c = cnt;
cnt++;
if (L == R) {
val[c] = y;
}
else {
int mid = (L+R)/2;
if (x <= mid) {
lef[c] = update(lef[tr],x,y,L,mid);
rig[c] = rig[tr];
}
else {
lef[c] = lef[tr];
rig[c] = update(rig[tr],x,y,mid+1,R);
}
val[c] = val[lef[c]] + val[rig[c]];
}
return c;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> N >> Q;
for (int i=1;i<=N;i++) {
cin >> X;
P[X].push_back(i);
}
ver[MAXP] = build(1,N);
for (int i=MAXP;i>1;i--) {
for (int x : P[i]) {
ver[i] = update(ver[i],x,1,1,N);
}
ver[i-1] = ver[i];
}
while (Q--) {
cin >> X >> Y;
int L = 2, R = MAXP, ans = 1;
while (L <= R) {
int mid = (L+R)/2;
if (query(ver[mid],X,Y,1,N) >= mid) {
ans = mid;
L = mid+1;
}
else {
R = mid-1;
}
}
cout << ans << "\n";
}
}
