#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n, q, cnt=1, mx=0;
int ver[maxn];
struct T
{
int x, no;
} a[maxn];
struct Node
{
int l, r, v;
Node() {};
Node(int x, int y, int z)
{
l=x; r=y; v=z;
}
} d[22*maxn];
bool lf(const T& i, const T& j)
{
return i.x>j.x;
}
void build(int i, int l, int r)
{
if (l==r) return;
d[i].l=++cnt; d[i].r=++cnt;
int mid=(l+r)/2;
build(d[i].l, l, mid);
build(d[i].r, mid+1, r);
}
int update(int i, int l, int r, int x)
{
int cur=++cnt;
if (l==r)
{
d[cur]=Node(0,0,1);
return cur;
}
d[cur]=d[i];
int mid=(l+r)/2;
if (x<=mid) d[cur].l=update(d[i].l, l, mid, x);
else d[cur].r=update(d[i].r, mid+1, r, x);
d[cur].v=d[d[cur].l].v+d[d[cur].r].v;
return cur;
}
int get(int i, int l, int r, int x, int y)
{
if (r<x || l>y) return 0;
if (x<=l && r<=y) return d[i].v;
int mid=(l+r)/2;
return get(d[i].l, l, mid, x, y)+get(d[i].r, mid+1, r, x, y);
}
int ssearch(int x)
{
int l=1, r=n;
while (l<=r)
{
int mid=(l+r)/2;
if (a[mid].x>=x) l=mid+1;
else r=mid-1;
}
return r;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i=1; i<=n; ++i)
{
cin >> a[i].x;
a[i].no=i;
mx=max(a[i].x, mx);
}
sort(a+1, a+n+1, lf);
build(1, 1, n);
ver[0]=1;
for (int i=1; i<=n; ++i)
ver[i]=update(ver[i-1], 1, n, a[i].no);
int x, y;
while (q--)
{
cin >> x >> y;
int l=1, r=mx;
while (l<=r)
{
int mid=(l+r)/2;
int s=ssearch(mid);
if (get(ver[s], 1, n, x, y)>=mid)
l=mid+1;
else r=mid-1;
}
cout << r << '\n';
}
}
