#include <bits/stdc++.h>
using namespace std;
struct tree {
int sum;
tree *lc, *rc;
tree() : sum(0), lc(nullptr), rc(nullptr) {};
tree(int x) : sum(x), lc(nullptr), rc(nullptr) {};
tree(tree *L, tree *R) {
sum = 0;
lc = L, rc = R;
if(lc) sum += lc->sum;
if(rc) sum += rc->sum;
}
};
const int mxn = 2e5 + 10;
int sum(tree *sus) { return sus->sum; }
int a[mxn], n, q;
tree *root[mxn];
tree *build(int tl, int tr) {
if(tl == tr) return new tree(0);
int tm = (tl + tr) / 2;
return new tree(build(tl, tm), build(tm + 1, tr));
}
tree *upt(tree *sus, int tl, int tr, int pos, int add) {
if(tl == tr) return new tree(sum(sus) + add);
int tm = (tl + tr) / 2;
if(pos <= tm) {
tree *LC = upt(sus->lc, tl, tm, pos, add);
return new tree(LC, sus->rc);
} else {
tree *RC = upt(sus->rc, tm + 1, tr, pos, add);
return new tree(sus->lc, RC);
}
return nullptr;
}
int query(tree *L, tree *R, int tl, int tr, int adder) {
if(tl == tr) return tr;
int tm = (tl + tr) / 2;
int cnt = sum(R->rc) - sum(L->rc) + adder;
// cout << "(" << tl << ") " << tm + 1 << " to " << tr << " = " << cnt << endl;
if(tm + 1 > cnt) return query(L->lc, R->lc, tl, tm, cnt);
return query(L->rc, R->rc, tm + 1, tr, adder);
}
void print(tree *sus, int tl, int tr) {
// cout << tl << " -> " << tr << ": " << sum(sus) << endl;
if(tl == tr) return;
int tm = (tl + tr) / 2;
print(sus->lc, tl, tm);
print(sus->rc, tm + 1, tr);
}
int main() {
cin >> n >> q;
root[0] = build(1, n);
for(int i = 1; i <= n; i++) {
cin >> a[i];
root[i] = upt(root[i - 1], 1, n, a[i], 1);
// print(root[i], 1, n);
// cout << endl;
}
while(q--) {
int l, r;
cin >> l >> r;
// cout << "query: " << l << ' ' << r << endl;
cout << query(root[l - 1], root[r], 1, n, 0) << endl;
}
return 0;
}
