#include <bits/stdc++.h>
using namespace std;
#define inf 0x3F3F3F3F
const int MXN = 2e5 + 5;
int n;
int a[MXN];
int st[MXN << 2];
int nxt[MXN], ind[MXN];
void make(int l, int r, int x, int ind, int val)
{
if (l == r)
{
st[x] = val;
return;
}
int mid = (l + r) >> 1;
if (ind <= mid) make(l, mid, 2*x, ind, val);
else make(mid + 1, r, 2*x + 1, ind, val);
st[x] = st[2*x] + st[2*x + 1];
}
int get(int l, int r, int x, int lx, int rx)
{
if (lx > rx) return 0;
if (l > rx || r < lx) return 0;
if (l >= lx && r <= rx) return st[x];
int mid = (l + r) >> 1;
return get(l, mid, 2*x, lx, rx) + get(mid + 1, r, 2*x + 1, lx, rx);
}
int findval(int l, int r, int x, int lx, int rx, int val)
{
if (lx > rx) return -1;
if (l > rx || r < lx) return -1;
if (l >= lx && r <= rx && st[x] < val) return -1;
if (l == r) return l;
int mid = (l + r) >> 1;
int A = findval(l, mid, 2*x, lx, rx, val);
if (A == -1) return findval(mid + 1, r, 2*x + 1, lx, rx, val - st[2*x]);
else return A;
}
int getind(int i)
{
int x = findval(1, n, 1, 1, n, i);
int ext = i - get(1, n, 1, 1, x - 1);
return ind[x] + ext - 1;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int Q;
cin >> n >> Q;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
ind[a[i]] = i;
}
vector<int> v;
for (int i = n; i >= 1; i--)
{
while (!v.empty() && a[v.back()] < a[i]) v.pop_back();
nxt[i] = (v.empty() ? n + 1 : v.back());
v.push_back(i);
}
int cur = 1;
while (cur < n + 1)
{
make(1, n, 1, a[cur], nxt[cur] - cur);
cur = nxt[cur];
}
array<int, 3> q[Q];
for (int i = 0; i < Q; i++)
{
cin >> q[i][0] >> q[i][1];
q[i][2] = i;
}
sort(q, q + Q);
int ans[Q];
int j = 0, f = 1;
for (array<int, 3> &i : q)
{
while (f && j < i[0])
{
int m = findval(1, n, 1, 1, n, n / 2);
if (get(1, n, 1, 1, m) == n / 2)
{
f = 0;
break;
}
int cur = getind(n / 2 + 1);
int tmp = cur;
while (cur < nxt[ind[m]])
{
nxt[cur] = min(nxt[cur], nxt[ind[m]]);
make(1, n, 1, a[cur], nxt[cur] - cur);
cur = nxt[cur];
}
nxt[ind[m]] = tmp;
make(1, n, 1, m, nxt[ind[m]] - ind[m]);
j++;
}
ans[i[2]] = a[getind(i[1])];
}
for (int i = 0; i < Q; i++) cout << ans[i] << '\n';
}
