#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_map>
#include <queue>
#define NEK 1000000007
#define ll long long
#define vec vector
#define For(i, n) for(int i = 0; i < n; i++)
#define pii pair<int, int>
#define ff first
#define int ll
#define ss second
#define ld long double
#define mod 1000000009
#define all(x) x.begin(), x.end()
using namespace std;
class intervalac{
int n;
vec<int> l, r, in;
void update(int s){
in[s] = in[s*2] + in[s*2 + 1];
}
public:
intervalac(int vel){
n = 1;
while(n < vel)n*=2;
l.resize(2*n); r.resize(2*n); in.resize(2*n, 0);
For(i, n){
l[i+n] = r[i+n] = i;
}
for(int i = n-1; i >= 1; i--){
l[i] = l[i*2];
r[i] = r[i*2 + 1];
}
}
void zmen(int a, int b){
a+=n;
in[a] = b;
a/=2;
while(a){
update(a);
a/=2;
}
return;
}
pii daj_box_aj_index(int k, int s = 1){
if(s >= n){
return {s-n, k};
}
if(k >= in[s*2]){
k -= in[s*2];
return daj_box_aj_index(k, s*2+1);
}
return daj_box_aj_index(k, s*2);
}
};
struct otazka{
int t, k, ind;
bool operator<(const otazka &o) const{
return t > o.t;
}
};
bool zorad(otazka a, otazka b){
return a.t > b.t;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, q; cin >> n >> q;
vec<int> p(n);
vec<int> vti(n, 0);
For(i, n) {cin >> p[i]; p[i]--; vti[p[i]] = i;}
vec<int> po(n, -1);
vec<pii> sh; sh.push_back({NEK, -1});
For(i, n/2){
while(sh.back().ff < p[i]){
po[sh.back().ss] = i;
sh.pop_back();
}
sh.push_back({p[i], i});
}
sh.clear();
sh.push_back({NEK, -1});
for(int i = n/2; i < n; i++){
while(sh.back().ff < p[i]){
po[sh.back().ss] = i;
sh.pop_back();
}
sh.push_back({p[i], i});
}
For(i, n){
if(i < n/2 && po[i] == -1){
po[i] = n/2;
}
if(i >= n/2 && po[i] == -1){
po[i] = n;
}
}
vec<otazka> o;
vec<int> odp(q);
For(i, q){
int t, k; cin >> t >> k; k--;
o.push_back({t, k, i});
}
sort(all(o));
while(!o.empty() && o.back().t == 0){
odp[o.back().ind] = p[o.back().k];
o.pop_back();
}
int som = 0;
vec<int> u(n, 0);
intervalac seg(n);
while(som < n){
u[p[som]] = po[som] - som;
seg.zmen(p[som], u[p[som]]);
som = po[som];
}
int cnt = 0;
while(1){
cnt++;
while(!o.empty() && (o.back().t == cnt)){
pii kol = seg.daj_box_aj_index(o.back().k);
odp[o.back().ind] = p[vti[kol.ff] + kol.ss];
o.pop_back();
}
pii kol = seg.daj_box_aj_index(n/2);
if(kol.ss == 0) break;
som = vti[kol.ff] + kol.ss;
u[kol.ff] = kol.ss;
seg.zmen(kol.ff, u[kol.ff]);
while(som < po[vti[kol.ff]]){
u[p[som]] = po[som] - som;
seg.zmen(p[som], u[p[som]]);
som = po[som];
}
}
while(!o.empty()){
pii kol = seg.daj_box_aj_index(o.back().k);
odp[o.back().ind] = p[vti[kol.ff] + kol.ss];
o.pop_back();
}
For(i, odp.size()){
cout << odp[i] + 1 << '\n';
}
return 0;
}
/*
int n, m; cin >> n >> m;
g.resize(n);
For(i, m){
int a, b, c; cin >> a >> b >> c; a--; b--;
}
cout << max_flow() << endl;
return 0;*/
