#include <iostream>
#include <vector>
#include <algorithm>
#define printff
#define printf
//#define printff(string, ...) printf(string, ##__VA_ARGS__); fflush(stdout)
#define MAXN 200000
#define LOG 19
int n, q;
int pos[MAXN+5];
int data[MAXN+5];
int next[MAXN+5];
int size[MAXN+5];
int sizer[MAXN+5];
void fwadd(int i, int x)
{
sizer[i] += x;
while (i <= n)
{
size[i] += x;
i += i & -i;
}
}
int fwget(int i)
{
int res = 0;
while (i >= 1)
{
res += size[i];
i -= i & -i;
}
return res;
}
#define pii std::pair<int, int>
// the last index i such that pref[i] <= n/2
pii fwsearch(int v=n/2)
{
int cur = 0;
int curs = 0;
for (int p = LOG-1; p >= 0; --p)
{
int nxc = cur + (1 << p);
if (nxc > n || curs + size[nxc] > v) continue;
curs += size[nxc];
cur = nxc;
}
return pii(cur, curs);
}
int gvcur = 0, gvcurs = 0;
int getvalue(int v=n/2+1)
{
printf("state (v=%i): ");
for (int i = 1; i <= n; ++i)
printf("%i ", fwget(i) - (i == 1 ? 0 : fwget(i-1)));
printf("\n");
int cur = 0;
int curs = 0;
for (int p = LOG-1; p >= 0; --p)
{
int nxc = cur + (1 << p);
if (nxc > n || curs + size[nxc] >= v) continue;
curs += size[nxc];
cur = nxc;
}
printff("detected cur: %i\n", cur);
cur++;
gvcur = cur;
gvcurs = curs;
return data[pos[cur] + v - curs - 1];
}
struct query_t
{
int t, i, r;
};
query_t queries[MAXN+5];
int res[MAXN+5];
signed main()
{
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
//printff("apakah sampai sini\n");
std::cin >> n >> q;
//printff("apakah sampai sini\n");
for (int i = 1; i <= n; ++i)
{
std::cin >> data[i];
pos[data[i]] = i;
next[i] = n+1;
//printf("apakah sampai sini\n");
}
next[n+1] = n+1;
std::vector<int> stack;
for (int i = 1; i <= n; ++i)
{
while (stack.size() && data[stack.back()] < data[i])
{
next[stack.back()] = i;
stack.pop_back();
}
stack.push_back(i);
}
for (int i = 1; i <= q; ++i)
{
std::cin >> queries[i].t >> queries[i].i;
queries[i].r = i;
}
std::sort(queries+1, queries+1+q, [](const query_t &a, const query_t &b){ return a.t < b.t; });
int qp = 1;
while (qp <= q && queries[qp].t == 0)
{
res[queries[qp].r] = data[queries[qp].i];
++qp;
}
int cur = 1;
while (cur != n+1)
{
fwadd(data[cur], next[cur] - cur);
printff("cur: %i\n", cur);
cur = next[cur];
}
printff("done with that\n");
int k = 1;
while (1)
{
// lb = last_block, totalsize/index
int now = getvalue();
if (sizer[now] != 0) break;
// 7 5 2 9 10 | 8 4 3 6 1
int last_index = pos[gvcur] + sizer[gvcur] - 1;
printff("last pos: %i, cur: %i, size: %i, us: %i, last index: %i, sub index: %i\n", pos[gvcur], gvcur, sizer[gvcur], gvcurs, last_index, now);
fwadd(gvcur, -(gvcurs + sizer[gvcur] - n/2));
while (1)
{
int now2i = std::min(next[pos[now]], last_index + 1);
printf("at current position (position %i): %i, next position: %i (contains %i)\n", pos[now], now, now2i, data[now2i]);
fwadd(now, now2i - pos[now]);
if (now2i > last_index) break;
now = data[now2i];
}
while (qp <= q && queries[qp].t <= k)
{
res[queries[qp].r] = getvalue(queries[qp].i);
++qp;
}
++k;
/*int A = sizer[gvcur]-(pos[now]-pos[gvcur]);
fwadd(gvcur,-A);
while (true)
{
int now2 = data[next[pos[now]]];
int B = pos[now2]-pos[now];
if (B >= A) break;
fwadd(now,B);
A -= B;
now = now2;
}
fwadd(now,A);*/
// @---@----@--|----@----
// sssssssss
}
while (qp <= q)
{
res[queries[qp].r] = getvalue(queries[qp].i);
++qp;
}
for (int i = 1; i <= q; ++i)
std::cout << res[i] << "\n";
return 0;
}
