#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
struct segtree{
int sz; vi sm;
void init(int n){
sz=n; sm.assign(4*n,0);
}
void update(int v, int tl, int tr, int pos, int val){
if (tl==tr) {sm[v]=val; return;}
int tm=(tl+tr)/2;
if (pos<=tm) update(2*v,tl,tm,pos,val);
else update(2*v+1,tm+1,tr,pos,val);
sm[v]=sm[2*v]+sm[2*v+1];
}
void update(int pos, int val) {update(1,0,sz-1,pos,val);}
ii get(int v, int tl, int tr, int val){
if (tl==tr) {return {tl,val};}
int tm=(tl+tr)/2;
if (sm[2*v]<val) return get(2*v+1,tm+1,tr,val-sm[2*v]);
return get(2*v,tl,tm,val);
}
ii get(int val){return get(1,0,sz-1,val);}
};
struct segtree2{
int sz; vi mx, a;
void init(int n, vi A){
sz=n; mx.assign(4*n,-1); a=A;
}
void build(int v, int tl, int tr){
if (tl==tr){mx[v]=tl; return;}
int tm=(tl+tr)/2;
build(2*v,tl,tm); build(2*v+1,tm+1,tr);
if (a[mx[2*v]]>a[mx[2*v+1]]) mx[v]=mx[2*v];
else mx[v]=mx[2*v+1];
}
int get(int v, int tl, int tr, int l, int r){
if (tl==l && tr==r) return mx[v];
if (l>r) return -1;
int tm=(tl+tr)/2;
int L=get(2*v,tl,tm,l,min(r,tm)); int R=get(2*v+1,tm+1,tr,max(l,tm+1),r);
if (L==-1) return R;
if (R==-1) return L;
if (a[L]<a[R]) return R;
return L;
}
int get(int l, int r){return get(1,0,sz-1,l,r);}
};
struct que{
int id, pos, t;
};
void solve(){
int n,q; cin>>n>>q;
vi a(n); FOR(i,0,n){ cin>>a[i]; a[i]--;}
segtree2 st2; st2.init(n,a); st2.build(1,0,n-1);
vi pos(n); FOR(i,0,n) pos[a[i]]=i;
vi sz(n);
vector<que> Q[n]; vi ans(q);
FOR(i,0,q){
que qr; cin>>qr.t>>qr.pos; qr.id=i; qr.pos--;
if (qr.t>=n) qr.t=n-1;
Q[qr.t].pb(qr);
}
segtree st; st.init(n);
vi used(n);
ROF(i,n-1,0){
if (used[i]) continue;
int L = pos[i]; int cnt=0;
while (L < n){
if (used[a[L]]) break;
cnt++; used[a[L]]=1; L++;
}
st.update(i,cnt); sz[i]=cnt;
//cout<<i<<" "<<cnt<<'\n';
}
FOR(i,0,n){
for (que qr : Q[i]){
ii val = st.get(qr.pos+1);
ans[qr.id] = a[pos[val.fi]+val.se-1];
}
ii val = st.get(n/2+1);
if (val.se == 1) continue;
int L=pos[val.fi]+val.se-1, R=pos[val.fi]+sz[val.fi]-1;
while(st2.get(L,R) != -1){
int mx = st2.get(L,R);
sz[a[mx]]=R-mx+1; st.update(a[mx],sz[a[mx]]);
R=mx-1;
}
sz[val.fi]=val.se-1; st.update(val.fi, sz[val.fi]);
}
FOR(i,0,q) cout<<ans[i]+1<<"\n";
}
int main(){
//MOD=MOD1;
ios::sync_with_stdio(false);
if (fopen("input.txt", "r")) {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
}
int TC = 1;
//cin >> TC;
FOR(i, 1, TC+1){
//cout << "Case #" << i << ": ";
solve();
}
return 0;
}
