#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
vector<int> ar, pos;
struct segtree{
int n, type, tl, tr, val, pos, el;
vector<int> st, a;
int base=0;
int merge(int x, int y){
if(type) return max(x, y);
return x + y;
}
segtree(int _n){
n = _n; type = 0;
st.resize(4*n);
}
segtree(int _n, vector<int> _a){
n = _n; a = _a; type = 1;
st.resize(4*n);
build(1, 0, n-1);
}
void build(int v, int l, int r){
if(l==r) st[v] = a[l];
else{
int mid = (l+r) / 2;
build(v*2, l, mid);
build(v*2+1, mid+1, r);
st[v] = merge(st[v*2], st[v*2+1]);
}
}
void upd(int v, int l, int r){
if(l==r) st[v] = val;
else{
int mid = (l+r) /2;
if(pos <= mid) upd(v*2, l, mid);
else upd(v*2+1, mid+1, r);
st[v] = merge(st[v*2], st[v*2+1]);
}
}
void update(int _pos, int va){
pos = _pos; val=va;
upd(1, 0, n-1);
}
array<int, 2> get1(int v, int l, int r){
if(l==r){
return {val-el-1, l};
}
else{
int mid = (l+r)/2;
if(el+st[v*2] >=val&&st[v*2]>0) return get1(v*2, l, mid);
el+=st[v*2];
return get1(v*2+1, mid+1, r);
}
}
array<int, 2> get(int h){
val = h, el = 0;
return get1(1, 0, n-1);
}
int get0(int v, int l, int r){
if(l>tr || r < tl) return 0;
else if(l>= tl && r<= tr) return st[v];
else{
int mid = (l+r) /2;
return merge(get0(v*2, l, mid), get0(v*2+1, mid+1, r));
}
}
int get(int l, int r){
tl = l; tr = r;
return get0(1, 0, n-1);
}
};
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
int n, m; cin >> n >> m;
vector<int> a(n);
for (auto &i: a) cin >> i, i--;
segtree st_sizes(n);
segtree st_max(n, a);
vector<array<int, 2>> val(n, {-1, -1});
int l=0;
for(int i=1; i<n; i++){
if(a[l]<a[i]){
val[a[l]]={l, i-1};
l=i;
}
}
ar = a;
pos.resize(n);
for(int i=0; i<n; i++) pos[a[i]]=i;
val[a[l]] = {l, n-1};
for(int i=0; i<n; i++){
if(val[i][0]!=-1){
st_sizes.update(i, val[i][1]-val[i][0]+1);
}
}
vector<array<int, 2>> q(m);
vector<int> ans(m);
for(auto &[i, l]: q) cin >> i >> l, i=min(i, n);
vector<int> id(m);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&](int a, int b){
return q[a][0] < q[b][0];
});
int it = 0;
for(auto i: id){
while(it < q[i][0]){
auto [value, g]=st_sizes.get(n/2);
int po = pos[g];
if(value==val[g][1]-val[g][0]+1){
it++;
continue;
}
int k =po+value+1;
int r = val[g][1];
while(k<=r){
int v = st_max.get(k, r);
val[v]={pos[v], r};
st_sizes.update(v, r-pos[v]+1);
r = pos[v]-1;
}
st_sizes.update(g, k-po);
val[g]={po, k-1};
it++;
}
auto [value, g]=st_sizes.get(q[i][1]);
ans[i]=a[pos[g]+value];
}
for(auto i: ans) cout<<i+1<<"\n";
}
