#include <bits/stdc++.h>
using namespace std;
#define sp << " " <<
//#define int long long
#define vi vector<int>
#define pb push_back
#define F(xxx,yyy) for (int xxx=1;xxx<=yyy;xxx++)
const int N = 2e5+1;
vi a(N);
vector<int> t[4*N];
vi merge(vi& a,vi& b) {
int ptr = 0;
int ptr2 = 0;
int sz1 = a.size();
int sz2 = b.size();
vi v;
while (ptr < sz1 && ptr2 < sz2) {
if (a[ptr] > b[ptr2]) v.pb(a[ptr++]);
else v.pb(b[ptr2++]);
}
while (ptr<sz1) {
v.pb(a[ptr++]);
}
while (ptr2<sz2) {
v.pb(b[ptr2++]);
}
return v;
}
void build(int node,int l,int r) {
if (l == r) {
t[node].pb(a[l]);
return;
}
int m = (l+r) >> 1;
build(2*node,l,m);
build(2*node+1,m+1,r);
t[node] = merge(t[2*node],t[2*node+1]);
}
int f(vi& v,int x) {
int l = 0;
int r = v.size()-1;
while (l<=r) {
int m = (l+r) >> 1;
if (v[m] < x) r = m-1;
else l = m+1;
}
return l;
}
int query(int node,int l,int r,int L,int R,int x) {
if (l > R || r < L) return 0;
if (l >= L && r <= R) return f(t[node],x);
int m = (l+r) >> 1;
return query(2*node,l,m,L,R,x)+query(2*node+1,m+1,r,L,R,x);
}
void solve() {
int n,q;
cin >> n >> q;
for (int i=1;i<=n;i++) cin >> a[i];
build(1,1,n);
while (q--) {
int l,r;
cin >> l >> r;
int L=1;
int R=n;
while (L<=R) {
int x = (L+R) >> 1;
int y = query(1,1,n,l,r,x);
//icout << x sp y << endl;
if (y >= x) L = x+1;
else R = x-1;
}
cout << R << endl;
}
}
signed main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
