#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>
#define endl '\n'
#define int ll
using namespace std;
struct block
{
int head, l, r;
bool operator<(const block &y) const
{
return head < y.head;
}
};
struct qry
{
int t, i, idx;
};
struct segtree
{
private:
vector<int> tree;
int n;
void update(int idx, int val, int v, int tl, int tr)
{
if (tl == tr)
tree[v] = val;
else
{
int m = (tl + tr) / 2;
if (idx <= m)
update(idx, val, 2 * v, tl, m);
else
update(idx, val, 2 * v + 1, m + 1, tr);
tree[v] = tree[2 * v] + tree[2 * v + 1];
}
}
pii query(int idx, int v, int tl, int tr)
{
if (tl == tr)
return {tl, idx};
else
{
int m = (tl + tr) / 2;
if (tree[2 * v] > idx)
return query(idx, 2 * v, tl, m);
else
return query(idx - tree[2 * v], 2 * v + 1, m + 1, tr);
}
}
public:
segtree(int _n)
{
n = _n;
tree.resize(4 * n, 0);
}
void update(int idx, int val)
{
return update(idx, val, 1, 0, n - 1);
}
pii query(int idx)
{
return query(idx, 1, 0, n - 1);
}
};
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int N, Q;
cin >> N >> Q;
vector<int> arr(N);
vector<int> nxt(N, -1), res(Q, 0);
for (int i = 0; i < N; i++)
cin >> arr[i];
vector<qry> queries(Q);
for (int i = 0; i < Q; i++)
{
cin >> queries[i].t >> queries[i].i;
queries[i].i--;
queries[i].t = min(queries[i].t, N);
queries[i].idx = i;
}
sort(queries.begin(), queries.end(), [](qry &a, qry &b)
{ return a.t < b.t; });
int q_idx = 0;
while (q_idx < Q && queries[q_idx].t == 0)
{
res[queries[q_idx].idx] = arr[queries[q_idx].i];
q_idx++;
}
stack<int> stk;
for (int i = N - 1; i >= 0; i--)
{
while (!stk.empty() && arr[stk.top()] < arr[i])
stk.pop();
nxt[i] = stk.empty() ? N : stk.top();
stk.push(i);
}
segtree tree(N + 1);
vector<block> block_props(N + 1);
set<block> blocks;
int block_cnt = 0;
for (int i = 0; i < N; i++)
{
block_props[arr[i]] = {arr[i], i, nxt[i] - 1};
blocks.insert({arr[i], i, nxt[i] - 1});
tree.update(arr[i], nxt[i] - i);
block_cnt++;
i = nxt[i] - 1;
}
vector<block> fixed_blocks;
int idx = N - 1;
int t = 0;
while (idx != N / 2 - 1)
{
block b = *blocks.rbegin();
blocks.erase(b);
int sz = b.r - b.l + 1;
idx -= sz;
if (idx + 1 >= N / 2)
{
fixed_blocks.push_back(b);
continue;
}
// we want to make the block smaller
int k = N / 2 - 1 - idx - 1;
blocks.insert({b.head, b.l, b.l + k});
block_props[b.head] = {b.head, b.l, b.l + k};
tree.update(b.head, k + 1);
idx += k + 1;
for (int i = b.l + k + 1; i <= b.r; i = nxt[i])
{
int j = nxt[i];
blocks.insert({arr[i], i, j - 1});
block_props[arr[i]] = {arr[i], i, j - 1};
tree.update(arr[i], j - i);
idx += j - i;
}
t++;
while (q_idx < Q && queries[q_idx].t == t)
{
int fidx = queries[q_idx].i;
pii fres = tree.query(fidx);
res[queries[q_idx].idx] = arr[block_props[fres.first].l + fres.second];
q_idx++;
}
}
while (q_idx < Q)
{
int fidx = queries[q_idx].i;
pii fres = tree.query(fidx);
res[queries[q_idx].idx] = arr[block_props[fres.first].l + fres.second];
q_idx++;
}
// while (!blocks.empty())
// {
// fixed_blocks.push_back(*blocks.rbegin());
// blocks.erase(*blocks.rbegin());
// }
// reverse(fixed_blocks.begin(), fixed_blocks.end());
for (int q : res)
cout << q << endl;
}
