#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<iomanip>
#include<fstream>
#include<cmath>
#define x first
#define l second.first
#define r second.second
#define int long long
#define N 400005
#define mod (int) 99824435
#define all(x) x.begin(), x.end()
#define mid(l, r) (l + r) / 2
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define connect(a, b) graph[a].push_back(b), graph[b].push_back(a)
#define YN(a) cout << (a ? "Yes" : "No") << endl;
#define size(v) (int) v.size()
#define debug cout << "!" << endl;
using namespace std;
set<pair<int, pair<int, int>>> st, ans;
vector<pair<pair<int, int>, int>> v;
vector<pair<int, pair<int, int>>> blocks;
vector<int> nxt(N + 1);
vector<int> f;
int a[N + 1];
int n, q;
int find(pair<int, pair<int, int>> p){
int l1 = 0, r1 = size(blocks) - 1;
while(l1 < r1){
int mid = mid(l1, r1);
if(blocks[mid] == p) return mid;
if(blocks[mid] > p) r1 = mid - 1;
else l1 = mid + 1;
}
return l1;
}
void find_block(){
auto k = st;
auto it = st.end();
int sum = 0;
for(int i = 0; i <= n; i++){
while(true){
it = st.end();
it--;
if(sum + (*it).r - (*it).l + 1 > n / 2) break;
sum += (*it).r - (*it).l + 1;
st.erase(it);
}
if(sum == n / 2) continue;
it = st.end();
it--;
int cur = n - (sum + (*it).r - (*it).l + 1);
int curi = (*it).l + (n / 2 - cur);
auto p = *it;
st.erase(it);
st.insert({p.x, {p.l, curi - 1}});
blocks.push_back({p.x, {p.l, curi - 1}});
while(curi <= p.r){
st.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
blocks.push_back({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
curi = nxt[curi];
}
}
st = k;
}
void add(int ind, int val){
while(ind < size(f)){
f[ind] += val;
ind += (ind & (-ind));
}
}
int count(int ind){
int sum = 0;
while(ind){
sum += f[ind];
ind -= (ind & (-ind));
}
return sum;
}
int find1(int val){
int l1 = 1, r1 = size(blocks);
while(l1 < r1){
int mid = mid(l1, r1);
if(count(mid) >= val) r1 = mid;
else l1 = mid + 1;
}
return l1;
}
void solve(){
cin >> n >> q;
for(int i = 1; i <= n; i++) nxt[i] = n + 1;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
stack<int> s;
for(int i = 1; i <= n; i++){
while(size(s) && a[s.top()] < a[i]){
nxt[s.top()] = i;
s.pop();
}
s.push(i);
}
int cnt = 0;
while(q--){
int i, t;
cin >> t >> i;
v.push_back({{min(n, t), i}, cnt++});
}
sort(all(v));
int mx = 0;
int L, R;
for(int i = 1; i <= n; i++){
if(mx > a[i]) R++;
else{
if(i != 1) st.insert({mx, {L, R}}), ans.insert({mx, {L, R}}), blocks.push_back({mx, {L, R}});
L = R = i;
}
mx = max(mx, a[i]);
}
st.insert({mx, {L, R}});
ans.insert({mx, {L, R}});
blocks.push_back({mx, {L, R}});
find_block();
sort(all(blocks));
f = vector<int>(size(blocks) + 1, 0);
for(auto k : st){
add(find(k) + 1, k.r - k.l + 1);
}
auto it = st.end();
int sum = 0, ind = 0;
vector<int> b(cnt, 0);
for(int i = 0; i <= n; i++){
while(ind != size(v) && v[ind].first.first == i){
int ind1 = find1(v[ind].first.second);
ind1--;
//cout << v[ind].first.first << ' ' << v[ind].first.second << ' ' << blocks[ind1].x << ' ' << blocks[ind1].l << ' ' << blocks[ind1].r << endl;
b[v[ind].second] = a[blocks[ind1].l + (v[ind].first.second - count(ind1)) - 1];
ind++;
}
while(true){
it = st.end();
it--;
if(sum + (*it).r - (*it).l + 1 > n / 2) break;
sum += (*it).r - (*it).l + 1;
st.erase(it);
}
if(sum == n / 2) continue;
it = st.end();
it--;
int cur = n - (sum + (*it).r - (*it).l + 1);
int curi = (*it).l + (n / 2 - cur);
auto p = *it;
add(find(p) + 1, -(p.r - p.l + 1));
ans.erase(ans.find(p));
st.erase(it);
st.insert({p.x, {p.l, curi - 1}});
ans.insert({p.x, {p.l, curi - 1}});
add(find({p.x, {p.l, curi - 1}}) + 1, curi - p.l);
while(curi <= p.r){
st.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
ans.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
add(find({a[curi], {curi, min(p.r, nxt[curi] - 1)}}) + 1, min(p.r, nxt[curi] - 1) - curi + 1);
curi = nxt[curi];
}
}
for(int k : b) cout << k << endl;
}
signed main(){
int q = 1;
//cin >> q;
while(q--){
solve();
}
}
