#include <bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int seg[N*25], lc[N*25], rc[N*25], version[N],n,q;
int node=0;
int update(int prv, int l, int r, int pos) {
int cur = ++node;
lc[cur] = lc[prv];
rc[cur] = rc[prv];
seg[cur] = seg[prv];
if (l==r) {
seg[cur]++;
return cur;
}
int mid=(r-l)/2+l;
if (pos<=mid) lc[cur] = update(lc[cur], l, mid, pos);
else rc[cur] = update(rc[cur], mid+1, r, pos);
seg[cur] = seg[lc[cur]] + seg[rc[cur]];
return cur;
}
int query(int idr, int idl, int l, int r, int ql, int qr) {
if (qr<l||r<ql) return 0;
if (ql<=l&&r<=qr) return seg[idr]-seg[idl];
int mid=(r-l)/2+l;
return query(lc[idr], lc[idl], l, mid, ql, qr) + query(rc[idr], rc[idl], mid+1, r, ql, qr);
}
int init(int l, int r) {
int cur = ++node;
if (l==r) return cur;
int mid=(r-l)/2+l;
lc[cur] = init(l,mid);
rc[cur] = init(mid+1,r);
return cur;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin>> n>> q;
init(1, N);
version[0] = 1;
for (int i=1; i<=n; i++) {
int x;
cin>> x;
version[i] = update(version[i-1], 1, N, x);
}
while (q--) {
int a,b;
cin>> a>> b;
int l=1, r=N;
while (l<=r) {
int mid=(r-l)/2+l;
if (query(version[b], version[a-1], 1, N, mid, N) >= mid) l=mid+1;
else r=mid-1;
}
cout<< l-1<< '\n';
}
}
