#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define pii pair<ll,ll>
#define all(a) a.begin(),a.end()
#define S second
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld long double
#define ll long long
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 3e6 , maxk = 100 + 10 , inf = 1e9+ 10 , mod = 1e9 + 9 ;
int mark[maxn] , ri[maxn] , ans[maxn] ;
int seg[4*maxn] ;
int n , q ;
void upd(int x, int w, int p =1 ,int l =1 ,int r = n){
int mid =(l+r)/2 , pl =p<<1 ,pr=p<<1|1 ;
if(l >x || x > r)return;
if(l==r){
seg[p] = w;
return ;
}
upd(x,w,pl,l,mid);
upd(x,w,pr,mid+1,r);
seg[p] = seg[pl] + seg[pr] ;
}
int que(int le , int ri , int p =1 ,int l =1 ,int r = n){
int mid =(l+r)/2 , pl =p<<1 ,pr=p<<1|1 ;
if(l >ri || le > r)return 0 ;
if(le <= l && r <= ri){
return seg[p] ;
}
return que(le,ri,pl,l,mid) + que(le,ri,pr,mid+1,r) ;
}
int find(int x ,int p =1 ,int l= 1, int r= n){
int mid = (l+r)/2 , pl =p << 1, pr =p<<1|1 ;
if(l == r)return l ;
if(seg[pl] < x){
x-=seg[pl] ;
return find(x,pr,mid+1,r);
}
return find(x,pl,l,mid);
}
int p[maxn] , a[maxn];
vector <pii> qu[maxn] ;
signed main(){
ios_base::sync_with_stdio(0) ;cin.tie(0) ;
cin >> n >> q;
rep(i ,1, n ){
cin >> a[i] ;
p[a[i]] = i ;
}
rep(i ,1, q){
int t , x;
cin >> t >> x;
t = min(t , n+1) ;
qu[t].pb({x,i}) ;
}
vector <int> vec;
int ls =n+1;
per(i , n ,1){
while(sz(vec) && a[vec.back()] <= a[i])vec.pop_back();
if(sz(vec) == 0){
ri[i] = n+1;
}else{
ri[i] = vec.back() ;
}
vec.pb(i);
}
int mx = 0 ;
rep(i ,1, n){
if(a[i] > a[mx]){
mark[a[i]] =1 ;
if(mx!=0)upd(a[mx] , i-mx) ;
mx = i ;
}
}
ri[n+1]= n+2;
mark[n] =1;
upd(n , n-mx+1) ;
rep(i ,0 , n+1){
for(auto [x,id] : qu[i]){
int z = find(x) ;
ans[id] = a[p[z] + x-que( 1, z-1) -1] ;
}
int x = find(n/2);
if(que(1,x)!=n/2){
int id = p[x] + n/2-que(1,x-1) ;
vector <int> vec;
while(id <= n+1){
vec.pb(id) ;
if(mark[a[id]] == 1)break ;
id = ri[id] ;
}
rep(i , 0 ,sz(vec)-2){
mark[a[vec[i]]] = 1;
if(i != sz(vec)-2){
upd(a[vec[i]] , vec[i+1]-vec[i]) ;
}else{
upd(a[vec[i]] , que(x,x)-(vec[i]-p[x]) ) ;
}
}
upd(x , vec[0]-p[x]) ;
}
}
rep(i ,1, q){
cout << ans[i] << "\n";
}
}
