#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = (119 << 23) | 1;
constexpr ull sqr = 223;
constexpr ld eps = 1e-9;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
long long random_ll(long long l, long long r) {if (l > r) return -1; return uniform_int_distribution<long long>(l, r)(rng);}
int n;
int a[100005];
pair <int, int> s[100005];
int bit[100005], nex[100005];
void update(int i, int val){
for(; i <= 1e5; i += i & -i) bit[i] += val;
}
int query(int i){
int ans = 0;
for(; i >= 1; i -= i & -i) ans += bit[i];
return ans;
}
set <pair <int, pair <int, int>>> ss;
void parti(int l, int r){
int cur = a[l];
while(l <= r){
int xx = min(r, nex[l]);
if(xx == -1) xx = r;
ss.insert({a[l], {l, xx}});
s[a[l]] = {l, xx};
update(a[l], xx - l + 1);
l = xx + 1;
}
}
void solve(){
return;
memset(bit, 0, sizeof(bit));
int m;
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> a[i];
nex[i] = - 1;
}
int cur = a[1];
stack <int> stt;
for(int i = 1; i <= n; i ++){
while(!stt.empty() && a[stt.top()] < a[i]){
nex[stt.top()] = i - 1;
stt.pop();
}
stt.push(i);
}
parti(1, n);
vector <pair <int, int>> q[n + 1];
int ww = 0;
for(int i = 1; i <= m; i ++){
int t, j;
cin >> t >> j;
q[min(t, n)].pb({j, i});
ww = t;
}
int res[m + 1];
for(int _ = 0; _ <= n; _ ++){
for(auto& x : q[_]){
int l = 1, r = n, ans = 1;
while(l <= r){
int mid = (l + r) >> 1;
if(query(mid) >= x.fr) ans = mid, r = mid - 1;
else l = mid + 1;
}
res[x.sc] = a[s[ans].fr + (x.fr - query(ans - 1) - 1)];
}
int l = 1, r = n, ans = n;
while(l <= r){
int mid = (l + r) >> 1;
int as = query(mid);
if(as == (n >> 1)){
ans = mid;
break;
}
if(as > (n >> 1)) r = mid - 1, ans = mid;
else l = mid + 1;
}
if(query(ans) != n / 2){
l = s[ans].fr, r = s[ans].sc;
s[ans] = {0, 0};
ss.erase({a[l], {l, r}});
update(ans, - (r - l + 1));
int prev = query(ans);
parti(l, l + n / 2 - prev - 1);
parti(l + n / 2 - prev, r);
}
// cout << l << "->" << l + n / 2 - prev - 1 << " " << l + n / 2 - prev << "->" << r << ": \n";
// for(auto& x : ss) cout << x.sc.fr << "->" << x.sc.sc << " "; cout << "\n";
}
for(int i = 1; i <= m; i ++) cout << res[i] << "\n";
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("TREE.inp", "r")){
freopen("TREE.inp", "r", stdin);
freopen("TREE.out", "w", stdout);
}
int t = 1;
// cin >> t;
while(t --){
solve();
// cout << "\n";
}
cerr << "Code time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
return 0;
}
// Whose eyes are those eyes?
