#include <bits/stdc++.h>
using namespace std;
const int maxn = 200005;
const int inf = 1e9;
int n, q;
int a[maxn];
pair<int, int> toAdd[maxn];
struct Node
{
int lc;
int rc;
int sum;
Node()
{
lc = rc = -1;
sum = 0;
}
};
Node tree[4 * maxn + 80 * maxn];
vector<pair<int, int>> roots;
int cntNodes = 0;
int update(int node, int l, int r, int pos)
{
int curr = ++cntNodes;
if (l == r)
{
tree[curr].sum = 1;
tree[curr].lc = tree[curr].rc = -1;
return curr;
}
tree[curr].lc = tree[node].lc;
tree[curr].rc = tree[node].rc;
int mid = (l + r) / 2;
if (pos <= mid)
{
tree[curr].lc = update(tree[curr].lc, l, mid, pos);
}
else
{
tree[curr].rc = update(tree[curr].rc, mid + 1, r, pos);
}
tree[curr].sum = tree[tree[curr].lc].sum + tree[tree[curr].rc].sum;
return curr;
}
int query(int node, int l, int r, int ql, int qr)
{
if (ql <= l && r <= qr)
{
return tree[node].sum;
}
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid)
{
res += query(tree[node].lc, l, mid, ql, qr);
}
if (qr >= mid + 1)
{
res += query(tree[node].rc, mid + 1, r, ql, qr);
}
return res;
}
void fastIO()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
int main()
{
fastIO();
//freopen("index.txt", "r", stdin);
//freopen("indexout.txt", "w", stdout);
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
cin >> a[i];
toAdd[i] = make_pair(a[i], i);
}
sort(toAdd + 1, toAdd + n + 1);
int currnum = 200001;
roots.push_back(make_pair(0, currnum));
for (int i = n; i >= 1; --i)
{
while (currnum > toAdd[i].first)
{
roots.push_back(make_pair(roots.back().first, --currnum));
}
if (currnum == toAdd[i].first)
{
roots.push_back(make_pair(update(roots.back().first, 1, n, toAdd[i].second), toAdd[i].first));
}
}
reverse(roots.begin(), roots.end());
for (int i = 1; i <= q; ++i)
{
int from, to;
cin >> from >> to;
int l = 0;
int r = roots.size() - 1;
while (l <= r)
{
int mid = (l + r) / 2;
if (query(roots[mid].first, 1, n, from, to) >= roots[mid].second)
{
l = mid + 1;
}
else
{
r = mid - 1;
}
}
cout << roots[r].second << "\n";
}
return 0;
}
