#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200001;
const int MAXNODES = MAXN * 200;
int val[MAXN];
struct Node {
int sum;
Node(int _sum=0): sum(_sum) {}
Node operator+(Node right) {
Node left = *this;
return Node(left.sum + right.sum);
}
};
struct SEG {
int n; vector<Node> seg; vector<int> ls, rs;
SEG(int _n=0) {
n = 1;
while (n < _n) n <<= 1;
seg.reserve(MAXNODES);
ls.reserve(MAXNODES);
rs.reserve(MAXNODES);
createNode();
createNode();
}
int createNode(int src = 0) {
seg.push_back(src == 0 ? Node() : seg[src]);
ls.push_back(src == 0 ? 0 : ls[src]);
rs.push_back(src == 0 ? 0 : rs[src]);
return (int)seg.size() - 1;
}
int getLeft(int v) {
return ls[v] = (ls[v] == 0 ? createNode() : ls[v]);
}
int getRight(int v) {
return rs[v] = (rs[v] == 0 ? createNode() : rs[v]);
}
int add(int v, int l, int r, int i, int x) {
v = createNode(v);
if (l == r) {
seg[v].sum += x;
return v;
}
int m = (l + r) / 2;
if (i <= m) ls[v] = add(getLeft(v), l, m, i, x);
else rs[v] = add(getRight(v), m+1, r, i, x);
seg[v] = seg[getLeft(v)] + seg[getRight(v)];
return v;
}
int findH(int vl, int vr, int l, int r, int bigger) {
if (l == r) return l;
int m = (l + r) / 2;
int right = seg[getRight(vr)].sum - seg[getRight(vl)].sum;
// cout << l << ' ' << r << ' ' << bigger << ' ' << right << endl;
if (m+1 <= bigger + right)
return findH(getRight(vl), getRight(vr), m+1, r, bigger);
else return findH(getLeft(vl), getLeft(vr), l, m, bigger + right);
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, qs; cin >> n >> qs;
for (int i=1; i<=n; i++) cin >> val[i];
SEG seg(MAXN);
vector<int> versions{1};
for (int i=1; i<=n; i++) {
versions.push_back(seg.add(versions.back(), 0, seg.n-1, val[i], 1));
}
for (int q=0; q<qs; q++) {
int l, r; cin >> l >> r;
cout << seg.findH(versions[l-1], versions[r], 0, seg.n-1, 0) << '\n';
}
return 0;
}
