#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;
vector<int> shf(vector<int> vec)
{
int n = vec.size();
vector<int> ans;
int p0 = 0, p1 = n/2;
Loop (_,0,n) {
if (p1 == n || (p0 < n/2 && vec[p0] < vec[p1]))
ans.push_back(vec[p0++]);
else
ans.push_back(vec[p1++]);
}
return ans;
}
const int N = 200'010;
void shf2(int *a, int n)
{
static int tmp[N];
int p = n/2;
while (p < n && a[p] < a[0])
++p;
memcpy(tmp, a+n/2, (p-n/2)*sizeof(*a));
memmove(a+p-n/2, a, (n/2)*sizeof(*a));
memcpy(a, tmp, (p-n/2)*sizeof(*a));
}
int ans[N];
vector<pii> Q[N];
int *ptr[N];
namespace fen {
const int lg = 18;
int a[1<<lg];
void add(int i, int x) {
++i;
while (i < (1<<lg)) {
a[i] += x;
i += i&-i;
}
}
int get(int r) {
int ans = 0;
while (r > 0) {
ans += a[r];
r -= r&-r;
}
return ans;
}
int get(int l, int r) { return get(r) - get(l); }
pii bin(int x) {
int ans = 0;
int sum = 0;
LoopR (i,0,lg) {
if (sum + a[ans + (1<<i)] <= x) {
sum += a[ans + (1<<i)];
ans += (1<<i);
}
}
return {ans, sum};
}
}
int sz[N];
int nxt[N];
int main()
{
cin.tie(0) -> sync_with_stdio(false);
int n, q;
cin >> n >> q;
vector<int> vec(n);
//iota(vec.begin(), vec.end(), 0);
//auto pleh = vec;
//int cntt = 0;
//for (;;) {
// int cnt = 0;
// vec = pleh;
// for (;;) {
// auto tmp = shf(vec);
// if (tmp == vec)
// break;
// vec = tmp;
// ++cnt;
// }
// cntt = max(cntt, cnt);
// if (!next_permutation(pleh.begin(), pleh.end()))
// break;
//}
//cout << cntt << '\n';
//return 0;
//mt19937_64 rd(chrono::high_resolution_clock::now().time_since_epoch().count());
//iota(vec.begin(), vec.end(), 0);
//shuffle(vec.begin(), vec.end(), rd);
for (int &x : vec)
cin >> x;
Loop (i,0,q) {
int t, p;
cin >> t >> p;
--p;
t = min(t, n);
Q[t].push_back({p, i});
}
for (auto [p, j] : Q[0])
ans[j] = vec[p];
int mx = -1;
Loop (i,0,n/2) {
if (vec[i] > mx) {
mx = vec[i];
ptr[mx] = &vec[i];
}
sz[mx]++;
}
mx = -1;
Loop (i,n/2,n) {
if (vec[i] > mx) {
mx = vec[i];
ptr[mx] = &vec[i];
}
sz[mx]++;
}
vector<int> st;
LoopR (i,0,n) {
while (st.size() && vec[st.back()] < vec[i])
st.pop_back();
if (!st.size())
nxt[i] = N;
else
nxt[i] = st.back() - i;
st.push_back(i);
}
Loop (i,0,N)
fen::add(i, sz[i]);
//vecs.push_back(vec);
Loop (i,0,n) {
for (auto [p, j] : Q[i+1]) {
auto [y, beforey] = fen::bin(p);
//cerr << y << ' ' << beforey << '\n';
ans[j] = ptr[y][p - beforey];
}
auto [x, before] = fen::bin(n/2);
if (before == n/2)
continue;
int cnt = (before + sz[x]) - n/2;
//cerr << x << " to rem " << cnt << ' ' << sz[x] << '\n';
sz[x] -= cnt;
fen::add(x, -cnt);
int *p = ptr[x] + sz[x];
//cerr << "first to split is " << *p << '\n';
int j = 0;
int rj = p - vec.data();
while (j < cnt) {
int g = min(cnt-j, nxt[rj]);
//cerr << p[j] << " added!\n";
sz[p[j]] += g;
fen::add(p[j], g);
ptr[p[j]] = p+j;
j += g;
rj += g;
}
//cerr << "hola!\n";
}
Loop (i,0,q)
cout << ans[i] << '\n';
}
