#include <iostream>
#include <vector>
using namespace std;
const int N = 1<<18;
int ft[N], a[N], Ans[N<<2], b[N], sz[N], st[N], Nxt[N];
vector<pair<int, int>> Qr[N];
vector<int> stk;
void Add(int i, int v){
sz[i] += v;
for (; i < N; i += i&-i)
ft[i] += v;
}
int get(int i, int ans = 0){
for (; i; i -= i&-i)
ans += ft[i];
return ans;
}
int get2(int k, int i = 1){
while (1){
if (ft[i + (i&-i)] < k)
i += i&-i;
else if (ft[i] >= k)
return i-1;
else
k -= ft[i++];
}
return -1;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, q;
cin>>n>>q;
for (int i=1;i<=n;i++)
cin>>a[i];
for (int i=1, t, id;i<=q;i++){
cin>>t>>id;
t = min(t, n);
if (t == 0)
Ans[i] = a[id];
else
Qr[t].push_back({id, i});
}
int l1 = 1, l2 = n / 2 + 1, m = 0, ind = 0;
while (ind < n){
if (l1 <= n / 2 and (l2 == n + 1 or a[l2] > a[l1]))
b[++ind] = a[l1++];
else
b[++ind] = a[l2++];
st[b[ind]] = ind;
m = max(m, b[ind]);
Add(m, 1);
}
for (int i=1;i<=n;i++){
while (stk.size() > 0 and b[stk.back()] < b[i])
Nxt[stk.back()] = i, stk.pop_back();
stk.push_back(i), Nxt[i] = n + 1;
}
for (int i=1;i<=n;i++){
for (auto [id, id2] : Qr[i]){
int k = get2(id) + 1, rem = id - get(k - 1);
Ans[id2] = b[st[k] + rem - 1];
}
int k = get2(n / 2) + 1, rem = get(k) - n / 2;
for (int j=st[k] + sz[k] - rem;j < st[k] + sz[k];j = Nxt[j])
Add(b[j], min(sz[k] + st[k], Nxt[j]) - j);
Add(k, -rem);
}
for (int i=1;i<=q;i++)
cout<<Ans[i]<<'\n';
}
