#include<bits/stdc++.h>
using namespace std;
mt19937 rng(0);//rng(time(nullptr));
using T = int;
struct node {
T val, ma;
int size;
size_t prior;
node *left, *right;
//node *par=nullptr; bool isleft=0; se serve get_pos
node(T v) : val(v), ma(v), size(1),
prior(rng()), left(0), right(0) {}
node* fix() {
ma = val, size = 1;
if (left) {
ma = max(ma, left->ma);
size += left->size;
}
if (right) {
ma = max(ma, right->ma);
size += right->size;
}
return this;
}
};
node* merge(node* a, node* b) {
if (!a) return b; a->fix();
if (!b) return a; b->fix();
if (a->prior > b->prior) {
auto tmp = merge(a->right, b);
a->right = tmp;
//if(tmp)tmp->par = a, tmp->isleft = 0; //x get_pos
return a->fix();
} else {
auto tmp = merge(a, b->left);
b->left = tmp;
//if(tmp)tmp->par = b, tmp->isleft = 1; //x get_pos
return b->fix();
}
}
//taglio subito dopo k elementi (1-based)
//es. k=1, divido il primo elemento dagli altri
pair<node*, node*> split(node* p, int k) {
if (!p) return {nullptr, nullptr};
p->fix();
int sl = p->left ? p->left->size : 0;
if (k <= sl) {
auto [a, b] = split(p->left, k);
//if(a) a->par = nullptr, a->isleft=0; //per get_pos
p->left = b;
//if(b) b->par = p, b->isleft = 1; //per get_pos
return {a, p->fix()};
} else {
auto [a, b] = split(p->right, k-sl-1);
//if(b) b->par = nullptr, b->isleft=0; //per get_pos
p->right = a;
//if(a) a->par = p, a->isleft = 0; //per get_pos
return {p->fix(), b};
}//invariante: sui due nodi di ritorno
} //è sempre stata chiamata ->fix()
// ritorna il k-esimo nodo (0-based)
int find_kth(node* p,int pos){
int sl = p->left ? p->left->size : 0;
if (p->left && pos < sl) {
return find_kth(p->left,pos);
} else if (p->right && pos > sl) {
return find_kth(p->right,pos - sl - 1);
} else {
return p->val;
}
}
int find_first(node *p,int val){
int sl = p->left ? p->left->size : 0;
if (p->left && p->left->ma > val) {
return find_first(p->left,val);
} else if (p->val > val){
return sl;
} else if (p->right && p->right->ma > val) {
return sl + 1 + find_first(p->right,val);
} else {
return p->size;
}
}
// build treap for [l,r)
node* build(vector<T>& A, int l, int r) {
if (l + 1 == r) return new node(A[l]);
int m = (l + r) / 2;
node* a = build(A, l, m);
node* b = build(A, m, r);
return merge(a, b);
}
const int MAXN = 200005, MAXQ = 1000006;
int n,q,ans[MAXQ],tmp[MAXN],cont;
vector<T> v;
vector<pair<int,int> > opz[MAXN];
node* root;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>q;
v.resize(n);
for(int i=0;i<n;i++){
cin>>v[i];
}
for(int i=0;i<q;i++){
int t,x;
cin>>t>>x;
opz[min(t,n)].emplace_back(x-1,i);
}
root = build(v,0,n);
for(int i=0;i<=n;i++){
for(auto [a,b] : opz[i]){
ans[b]=find_kth(root,a);
}
auto [a,b] = split(root,n/2);
while(b!=nullptr){
int val = find_kth(b,0);
if(val > a->ma){
a = merge(a,b);
break;
}
int pos1 = find_first(a,val);
int pos2 = find_first(b,val);
auto [c,d] = split(b,pos2);
auto [e,f] = split(a,pos1);
a = merge(merge(e,c),f);
b = d;
cont++;
}
root = a;
}
for(int i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
