/***********************************************
* auth: tapilyoca *
* date: 07/07/2025 at 22:42:20 *
* dots: https://github.com/tapilyoca/dotilyoca *
***********************************************/
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
template<typename T>
using vec = vector<T>;
using ll = long long;
using vll = vec<ll>;
using vvll = vec<vll>;
using pll = pair<ll,ll>;
using str = string;
#define pb push_back
#define dbg(x) if(1) cerr << #x << ": " << x << endl;
/***********************************************/
struct Segment {
ll front, sstart, send, size;
Segment() : sstart(0), send(0), front(0), size(0) {}
Segment(ll s, ll e, ll f) {
sstart = s;
send = e;
front = f;
size = e-s+1;
}
bool operator>(const Segment&two) const {
return front > two.front;
}
bool operator<(const Segment&two) const {
return front < two.front;
}
void print() {
cerr << front << ": (" << sstart << ", " << send << ") ";
}
};
struct Query {
ll t, x;
Query() : t(0), x(0) {}
Query(ll tt, ll xx) {
t = tt;
x = xx;
}
};
vll riffle(vll &at) {
vll a, b;
ll n = at.size();
for(int i = 0; i < n/2; i++) {
a.pb(at[i]);
}
for(int j = n/2; j < n; j++) {
b.pb(at[j]);
}
vll out;
ll lp = 0, rp = 0;
while(lp != n/2 and rp != n/2) {
if(a[lp] < b[rp]) {
out.pb(a[lp]);
lp++;
} else {
out.pb(b[rp]);
rp++;
}
}
for(int i = lp; i < n/2; i++) out.pb(a[i]);
for(int i = rp; i < n/2; i++) out.pb(b[i]);
return out;
}
inline vll segmentize(vll &a) {
ll n = a.size();
stack<pll> st;
vll out(n,1e18);
for(int i = n-1; i >= 0; i--) {
while(!st.empty() and st.top().first < a[i]) st.pop();
if(!st.empty()) out[i] = st.top().second;
// cerr << i << " " << out[i] << endl;
st.push({a[i],i});
}
return out;
}
void bruh(set<Segment> s) {
for(auto itr = s.begin(); itr != s.end(); itr++) {
Segment x = *itr;
x.print();
}
}
void solve() {
ll n, q;
cin >> n >> q;
vll state(n,0);
for(int i = 0; i < n; i++) {
cin >> state[i];
}
ll T = -1;
vec<Query> queries(q);
for(int i = 0; i < q; i++) {
ll a, b;
cin >> a >> b;
b--;
queries[i] = Query(a,b);
T = a;
}
vll stateTwo = riffle(state);
vll next_seg = segmentize(stateTwo);
set<Segment> curr_state;
for(ll at = 0; at != 1e18; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] == 1e18 ? n-1 : next_seg[at] - 1);
curr_state.insert(Segment(one,two,stateTwo[at]));
}
set<Segment> done_states;
ll state_size = n;
for(int shuffles = 1; shuffles < T; shuffles++) {
// dbg(shuffles);
while(state_size > n/2) {
if(state_size - (*prev(curr_state.end())).size < n/2) break;
done_states.insert(*prev(curr_state.end()));
state_size -= (*prev(curr_state.end())).size;
curr_state.erase(prev(curr_state.end()));
// cerr << "hee hee hee haw" << endl;
}
if(state_size == n/2) break;
// get the middle seg
Segment midSeg = *curr_state.rbegin();
curr_state.erase(prev(curr_state.end()));
// midSeg.print();
ll newSS = state_size - midSeg.size;
// dbg(newSS);
// dbg(state_size);
// dbg(midSeg.size);
curr_state.insert(Segment(midSeg.sstart, midSeg.sstart + (n/2 - newSS) - 1, midSeg.front));
// resegment it
for(ll at = midSeg.sstart + (n/2 - newSS); at <= midSeg.send; at = next_seg[at]) {
ll one = at;
ll two = (next_seg[at] > midSeg.send ? midSeg.send : next_seg[at] - 1);
curr_state.insert(Segment(one,two,stateTwo[at]));
}
// cerr << "end of " << shuffles << " have ";
// bruh(curr_state);
// cerr << endl;
}
// cerr << "State finalized" << endl;
vll finalState;
for(auto itr = done_states.begin(); itr != done_states.end(); itr++) {
curr_state.insert(*itr);
}
while(!curr_state.empty()) {
Segment coolbeans = *curr_state.begin();
// coolbeans.print();
curr_state.erase(curr_state.begin());
for(ll i = coolbeans.sstart; i <= coolbeans.send; i++) finalState.pb(stateTwo[i]);
}
// cerr << "\nFinal state: ";
// for(ll &x : finalState) cerr << x << " ";
// cerr << endl;
for(Query &q : queries) {
cout << finalState[q.x] << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--) {
solve();
}
return 0;
}
/*
7 5 2 8 4 3 6 1 9 10
3 6 1 7 5 2 8 4 9 10
2 3 6 1 7 5 8 4 9 10
*/
