#include <iostream>
#include <vector>
using namespace std;
const int N = 1<<18;
int ft[N], a[N], Ans[N<<2];
vector<int> vec[N];
vector<pair<int, int>> Qr[N];
void Add(int i, int 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, b, cnt = 0;
while (l1 <= n / 2 or l2 <= n){
if (l1 <= n / 2 and (l2 == n + 1 or a[l2] > a[l1]))
b = a[l1++];
else
b = a[l2++];
m = max(m, b);
vec[m].push_back(b);
Add(m, 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] = vec[k][rem - 1];
}
int k = get2(n / 2) + 1, rem = get(k) - n / 2;
m = 0;
Add(k, -rem);
int sz = vec[k].size();
for (int j=sz - rem;j < sz;j++){
m = max(m, vec[k][j]), vec[m].push_back(vec[k][j]), Add(m, 1);
cnt++;
if (cnt > 1e7)
cout<<1 / 0;
}
while (rem--)
vec[k].pop_back();
}
for (int i=1;i<=q;i++)
cout<<Ans[i]<<'\n';
}
