#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;
struct node {
long long sum = 0;
node *l = nullptr, *r = nullptr;
int L, R;
node(int L, int R) : L(L), R(R) {}
void create_kids() {
int mid = (L+R)/2;
if (l == nullptr)
l = new node(L, mid);
if (r == nullptr)
r = new node(mid, R);
}
node* update(int ind, int x) {
if (R - L == 1) {
node* new_node = new node(L, R);
new_node->sum = sum + x;
return new_node;
}
node* new_node = new node(L, R);
int mid = (L+R)/2;
if (l == nullptr) l = new node(L, mid);
if (r == nullptr) r = new node(mid, R);
new_node->l = l;
new_node->r = r;
if (ind < mid) {
new_node->l = l->update(ind, x);
} else {
new_node->r = r->update(ind, x);
}
new_node->sum = new_node->l->sum + new_node->r->sum;
return new_node;
}
long long query(int ql, int qr) {
if (ql <= L && R <= qr) {
return sum;
}
if (qr <= L || R <= ql) return 0;
return (l == nullptr ? 0 : l->query(ql, qr))
+ (r == nullptr ? 0 : r->query(ql, qr));
}
void dfs() {
cout << L << " " << R << " " << sum << '\n';
if (l != nullptr)
l->dfs();
if (r != nullptr)
r->dfs();
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int A = 200001;
int n,q; cin >> n >> q;
vector<node*> roots { new node(0, A) };
for (int i = 0; i < n; i++) {
int ai; cin >> ai;
roots.push_back(roots.back());
roots.back() = roots.back()->update(ai, 1);
}
while (q--) {
int l,r; cin >> l >> r;
l--;
auto root_l = roots[l];
auto root_r = roots[r];
int sum = 0;
while (root_l -> R - root_l -> L > 1) {
assert(root_l ->L == root_r ->L);
assert(root_l ->R == root_r ->R);
root_l -> create_kids();
root_r -> create_kids();
int x = sum + root_r -> r -> sum - root_l -> r -> sum;
int mid = (root_r -> L + root_r -> R)/2;
if (mid <= x) {
root_r = root_r->r;
root_l = root_l->r;
} else {
root_r = root_r->l;
root_l = root_l->l;
sum = x;
}
}
cout << root_r -> L << endl;
}
}
