#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef vector<int> vi;
typedef vector< vector <int> > vvi;
typedef pair<int, int> pii;
typedef pair < pair < int, int >, int > piii;
typedef pair < pair <int, int > , pair <int, int> > piiii;
typedef pair<ll, ll> pll;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
#define FOR(i,a,b) for(int i = a; i < b; i ++)
#define RFOR(i,a,b) for(int i = a-1; i >= b; i --)
#define all(a) a.begin(), a.end()
#define endl '\n';
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
template <typename T>
void pr(vector<T> &v) {
FOR(i, 0, sz(v)) cout << v[i] << " ";
cout << endl;
}
template <typename T>
void pr(vector<vector<T> > &v) {
FOR(i, 0, sz(v)) { pr(v[i]); }
}
template <typename T>
void re(T &x) {
cin >> x;
}
template <typename T>
void re(vector<T> &a) {
FOR(i, 0, sz(a)) re(a[i]);
}
template <class Arg, class... Args>
void re(Arg &first, Args &... rest) {
re(first);
re(rest...);
}
template <typename T>
void pr(T x) {
cout << x << endl;
}
template <class Arg, class... Args>
void pr(const Arg &first, const Args &... rest) {
cout << first << " ";
pr(rest...);
cout << endl;
}
void ps() { cout << endl; }
template<class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
cout << t; if (sizeof...(ts)) cout << " "; ps(ts...);
}
const ll MOD = 1000000007;
#define inf 1e18;
#define INF INT_MAX;
long double PI = 4*atan(1);
long double eps = 1e-8;
int N, q;
int n;
vi a;
vector<array<int, 3>> qs;
struct seg {
int v, l, r;
bool operator<(const seg& o) const {
return v < o.v;
}
};
map<seg, int> segidx;
set<seg> segs;
vector<seg> allsegs;
int st[2000000] = {};
void update(int p, int l, int r, int idx, int v) {
if(l == r) {
st[p] = v;
return;
}
int m = (l + r)/2;
if(idx <= m) {
update(2*p, l, m, idx, v);
} else {
update(2*p + 1, m+1,r, idx, v);
}
st[p] = st[2*p] + st[2*p+1];
return;
}
int query(int p, int l, int r, int v) {
if(l == r) {
return a[allsegs[l].l + v - 1];
}
int m = (l+r)/2;
if(st[2*p] >= v) {
return query(2*p, l, m, v);
}
return query(2*p + 1, m + 1, r, v - st[2*p]);
}
vi bruteans;
vi brute() {
vi b = a;
int t = 0;
vi c = b;
int qidx = 0;
vi ans(q);
while(true) {
while(qidx < q && qs[qidx][0] == t) {
ans[qs[qidx][2]] = b[qs[qidx][1] - 1];
qidx++;
}
c.clear();
int lp = 0;
int rp = 0;
while(lp < n && rp < n) {
if(b[lp] < b[n + rp]) {
c.pb(b[lp]); lp++;
} else {
c.pb(b[n + rp]); rp++;
}
}
while(lp < n) {c.pb(b[lp]); lp++;}
while(rp < n) {c.pb(b[n + rp]); rp++;}
if(c == b) break;
b = c;
t++;
}
while(qidx < q) {
ans[qs[qidx][2]] = b[qs[qidx][1] - 1];
qidx++;
}
return ans;
}
int main() {
//auto start = chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);cin.tie(0);
// freopen("promote.in", "r", stdin);
// freopen("promote.out", "w", stdout);
#ifdef DEBUG
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin >> N >> q;
n = N/2;
a.resize(N); re(a);
FOR(i,0,q) {
int t,id; cin >> t >> id;
qs.pb({t, id, i});
}
sort(all(qs));
// vi bruteans = brute();
stack<int> stk;
vi nxt(N);
FOR(i,0,N) {
while(!stk.empty() && a[i] > a[stk.top()]) {
nxt[stk.top()] = i - 1;
stk.pop();
}
stk.push(i);
}
while(!stk.empty()) {
int c = stk.top(); stk.pop();
nxt[c] = N-1;
}
for(int i = 0; i < N; i = nxt[i] + 1) {
segs.insert({a[i], i, nxt[i]});
allsegs.pb({a[i], i, nxt[i]});
}
int len = N;
while(len > n) {
auto p = segs.rbegin();
int clen = (*p).r - (*p).l + 1;
while(len - clen >= n) {
segs.erase(*p);
len -= clen;
if(!segs.empty()) p = segs.rbegin();
clen = (*p).r - (*p).l + 1;
}
if(len > n) {
int l = (*p).l;
int r = (*p).r;
segs.erase(*p);
int r1 = l + n - (len - clen) - 1;
allsegs.pb({a[l], l, r1});
segs.insert({a[l], l , r1});
r1++;
while(r1 <= r) {
int r2 = min(nxt[r1], r);
allsegs.pb({a[r1], r1, r2});
segs.insert({a[r1], r1, r2});
r1 = r2 + 1;
}
}
}
sort(all(allsegs));
int m = allsegs.size();
FOR(i,0,m) segidx[allsegs[i]] = i;
segs.clear();
vi ans(q);
int t = 0;
int qidx = 0;
for(int i = 0; i < N; i = nxt[i] + 1) {
segs.insert({a[i], i, nxt[i]});
int segid = segidx[{a[i], i, nxt[i]}];
update(1, 0, m, segid, nxt[i] - i + 1);
}
while(qidx < q && qs[qidx][0] == t) {
ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
qidx++;
}
len = N;
while(len > n) {
auto p = segs.rbegin();
int clen = (*p).r - (*p).l + 1;
while(len - clen >= n) {
int segid = segidx[*p];
// update(1, 0, m, segid, 0);
segs.erase(*p);
len -= clen;
if(!segs.empty()) p = segs.rbegin();
clen = (*p).r - (*p).l + 1;
}
if(len > n) {
int l = (*p).l;
int r = (*p).r;
int segid = segidx[*p];
update(1, 0, m, segid, 0);
segs.erase(*p);
int r1 = l + n - (len - clen) - 1;
segs.insert({a[l], l , r1});
segid = segidx[{a[l], l , r1}];
update(1, 0, m, segid, r1 - l + 1);
r1++;
while(r1 <= r) {
int r2 = min(nxt[r1], r);
segs.insert({a[r1], r1, r2});
segid = segidx[{a[r1], r1, r2}];
update(1, 0, m, segid, r2 - r1 + 1);
r1 = r2 + 1;
}
}
t++;
while(qidx < q && qs[qidx][0] == t) {
ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
qidx++;
}
}
while(qidx < q) {
ans[qs[qidx][2]] = query(1, 0, m, qs[qidx][1]);
qidx++;
}
FOR(i,0,q) {
cout << ans[i] << endl;
}
// auto stop = chrono::high_resolution_clock::now();
// auto duration = chrono::duration_cast<chrono::microseconds>(stop - start);
// cout << duration.count() << endl;
//cin.close();
//cout.close();
}
