#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
vector<int> sznost;
struct ST{
int l, r;
ST *lt, *rt;
int sz;
void comb() {
sz = lt->sz + rt->sz;
}
ST(int bl, int br) {
l = bl, r = br;
lt = rt = nullptr;
sz = 0;
if(l != r) {
int m = (l+r)/2;
lt = new ST(l, m);
rt = new ST(m+1, r);
}
}
void set(int i, int x) {
if(l == r) {
sznost[i] = x;
sz = x;
} else {
if(i <= lt->r) lt->set(i, x);
else rt->set(i, x);
comb();
}
}
// returns the leader (and the ) of the group that contains the value at the i-th index
pair<int, int> find(int i) {
if(l == r) return make_pair(l, i);
if(lt->sz < i) return rt->find(i - (lt->sz));
return lt->find(i);
}
};
int main() {
fastIO;
int n, q; cin >> n >> q;
sznost = vector<int>(n, 0);
vector<int> a(n); for(auto &i : a) cin >> i;
struct Query{
int t, i, qi, ans;
Query(int a, int b, int c): t(a), i(b), qi(c), ans(-1) {};
bool operator<(const Query &other) const {
return t < other.t;
}
};
vector<Query> qs;
qs.reserve(q);
for(int i = 0; i < q; i++) {
int a, b; cin >> a >> b;
qs.push_back(Query(a, b, i));
}
sort(qs.begin(), qs.end());
vector<int> rev(n);
ST szs(0, n-1);
for(int i = 0; i < n; i++) {
a[i]--;
rev[a[i]] = i;
}
bool fixed = false;
auto reprocessrange = [&](int s, int t) {
// printf("running [%d, %d)", s, t);
int runmx = -1;
int sz = 0;
for(int i = s; i <= t; i++) {
if(i == t) {
// printf("%d %d\n", runmx, sz);
szs.set(runmx, sz);
} else {
if(runmx < a[i]) {
// printf("%d %d\n", runmx, sz);
if(runmx != -1) szs.set(runmx, sz);
runmx = a[i];
sz = 1;
} else sz++;
}
}
// for(int i = 0; i < n; i++) printf("%d %d\n", i, szs.getsz(i));
// printf("\n");
};
int time = 0;
auto update = [&](){
pair<int, int> lead = szs.find(n/2 + 1);
// printf("update! leader is %d, and the index is %d.\n", lead.first, lead.second);
if(lead.second == 1) {
fixed = true;
return;
}
int sz = sznost[lead.first];
reprocessrange(rev[lead.first]+lead.second-1, rev[lead.first]+sz);
szs.set(lead.first, lead.second-1);
// printf("correct update after reassign:\n");
// for(int i = 0; i < n; i++) printf("%d %d\n", i, szs.getsz(i));
// printf("\n");
time++;
};
auto get = [&](int i){
pair<int, int> lead = szs.find(i);
// printf("%d %d %d %d %d\n", time, i, lead.first, lead.second, a[rev[lead.first] + lead.second - 1] + 1);
return a[rev[lead.first] + lead.second - 1] + 1;
};
reprocessrange(0, n);
for(int i = 0; i < q;) {
if(fixed) {
qs[i].ans = get(qs[i].i);
i++;
} else {
if(qs[i].t == time) {
qs[i].ans = get(qs[i].i);
i++;
} else update();
}
}
vector<int> ans(q); for(auto qx : qs) ans[qx.qi] = qx.ans;
for(auto &i : ans) cout << i << '\n';
return 0;
}
