#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;
const int N = 1e5+1;
struct ST {
vi t;
ST(int nn) {
t.assign(4*nn+1,0);
}
void update(int node,int l,int r,int p,int v) {
if (l == r) {
t[node] = v;
return;
}
int m = (l+r) >> 1;
if (p <= m) update(2*node,l,m,p,v);
else update(2*node+1,m+1,r,p,v);
t[node] = t[2*node]+t[2*node+1];
}
int walk(int node,int l,int r,int x) {
if (t[node] < x) assert(0);
if (l == r) return l;
int m = (l+r) >> 1;
if (t[2*node] >= x) return walk(2*node,l,m,x);
return walk(2*node+1,m+1,r,x-t[2*node]);
}
int query(int node,int l,int r,int L,int R) {
if (l > R || r < L) return 0;
if (l >= L && r <= R) return t[node];
int m = (l+r) >> 1;
return query(2*node,l,m,L,R)+query(2*node+1,m+1,r,L,R);
}
};
void solve() {
int n,q;
cin >> n >> q;
vi a(n+1);
for (int i=1;i<=n;i++) cin >> a[i];
using Query = pii;
vector<Query> queries[n+1];
vi ans(q+1);
for (int i=1;i<=q;i++) {
int t,p;
cin >> t >> p;
t = min(t,n);
queries[t].push_back({p,i});
}
vi pos(n+1);
for (int i=1;i<=n;i++) pos[a[i]] = i;
vi R(n+1);
stack<int> stk;
for (int i = n;i>=1;i--) {
while (!stk.empty() && a[stk.top()] < a[i]) stk.pop();
if (stk.empty()) R[i] = n+1;
else R[i] = stk.top();
stk.push(i);
}
for (auto it : queries[0]) ans[it.ss] = a[it.ff];
ST st(n);
st.update(1,1,n,a[1],n/2);
st.update(1,1,n,a[n/2+1],n/2);
auto fix = [&](int v) -> void {
int cur = pos[v],curv = v;
while (1) {
int nxt = R[cur];
int mine = st.query(1,1,n,curv,curv);
if (nxt > cur+mine-1) break;
st.update(1,1,n,curv,nxt-cur);
st.update(1,1,n,a[nxt],mine-(nxt-cur));
cur = nxt,curv = a[nxt];
}
};
fix(a[1]);
fix(a[n/2+1]);
auto riffle = [&]() -> void {
int w = st.walk(1,1,n,n/2);
if (st.query(1,1,n,1,w) == n/2) return;
//w ile başlayan block kesilir.
int prv = st.query(1,1,n,1,w-1);
int mine = st.query(1,1,n,w,w);
int nxtt = a[pos[w]+n/2-prv];
st.update(1,1,n,nxtt,mine-(n/2-prv));
st.update(1,1,n,w,n/2-prv);
fix(w);
fix(nxtt);
};
for (int i=0;i<n;i++) {
if (i) riffle();
for (auto it : queries[i+1]) {
int w = st.walk(1,1,n,it.ff);
ans[it.ss] = a[pos[w]+(it.ff-st.query(1,1,n,1,w-1))-1];
}
}
for (int i=1;i<=q;i++) cout << ans[i] << '\n';
}
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef Dodi
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
int t = 1;
//cin >> t;
while (t --> 0) solve();
}
