#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int inf = 1e9;
int n, q;
int a[maxn];
vector<int> tree[4 * maxn];
vector<int> combine(const vector<int>& lhs, const vector<int>& rhs)
{
vector<int> res;
int lptr = 0;
int rptr = 0;
for (int i = 0; i < lhs.size() + rhs.size(); ++i)
{
int lnum = (lptr == lhs.size() ? inf : lhs[lptr]);
int rnum = (rptr == rhs.size() ? inf : rhs[rptr]);
if (lnum < rnum)
{
res.push_back(lnum);
++lptr;
}
else
{
res.push_back(rnum);
++rptr;
}
}
return res;
}
void build(int node, int l, int r)
{
if (l == r)
{
tree[node].push_back(a[l]);
return;
}
int mid = (l + r) / 2;
build(2 * node, l, mid);
build(2 * node + 1, mid + 1, r);
tree[node] = combine(tree[2 * node], tree[2 * node + 1]);
}
int query(int node, int l, int r, int ql, int qr, int val)
{
if (l > qr || r < ql)
{
return 0;
}
if (ql <= l && r <= qr)
{
return tree[node].size() - (lower_bound(tree[node].begin(), tree[node].end(), val) - tree[node].begin());
}
int mid = (l + r) / 2;
return query(2 * node, l, mid, ql, qr, val) + query(2 * node + 1, mid + 1, r, ql, qr, val);
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
}
build(1, 1, n);
for (int i = 1; i <= q; ++i)
{
int from, to;
cin >> from >> to;
int l = 1;
int r = maxn;
while (l <= r)
{
int mid = (l + r) / 2;
if (query(1, 1, n, from, to, mid) >= mid)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << r << "\n";
}
return 0;
}
