#include <bits/stdc++.h>
using namespace std;
struct node {
int val, left, right;
};
struct pst {
vector<node> seg;
vector<int> arr;
int n, cnt;
void init(int sz) {
n = sz;
seg.assign(50*n, {0, 0, 0});
cnt = 0;
}
int clone(int node) {
seg[++cnt] = seg[node];
return cnt;
}
int build(int l, int r, int node) {
cnt = max(cnt, node);
if(l == r) {
seg[node].val = 0;
return node;
}
int mid = (l+r)/2;
seg[node].left = build(l, mid, node*2);
seg[node].right = build(mid+1, r, node*2+1);
seg[node].val = seg[seg[node].left].val + seg[seg[node].right].val;
return node;
}
int update(int l, int r, int idx, int val, int node) {
int now = clone(node);
if(l == r) {
seg[now].val += val;
return now;
}
int mid = (l+r)/2;
if(idx <= mid) seg[now].left = update(l, mid, idx, val, seg[node].left);
else seg[now].right = update(mid+1, r, idx, val, seg[node].right);
seg[now].val = seg[seg[now].left].val + seg[seg[now].right].val;
return now;
}
int walk(int l, int r, int n1, int n2, int sum) {
if(l == r) return l;
int mid = (l+r)/2;
int rcnt = seg[seg[n1].right].val - seg[seg[n2].right].val;
if(sum + rcnt <= mid) return walk(l, mid, seg[n1].left, seg[n2].left, sum+rcnt);
else return walk(mid+1, r, seg[n1].right, seg[n2].right, sum);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q, cnt=1, mxn=200000;
cin >> n >> q;
vector<int> arr(n+2, 0), rt(n+2, 0);
pst seg;
seg.init(mxn);
seg.build(1, mxn, 1);
rt[0] = 1;
for(int i=1; i<=n; i++) {
cin >> arr[i];
rt[i] = seg.update(1, mxn, arr[i], 1, rt[i-1]);
}
while(q--) {
int l, r;
cin >> l >> r;
cout << seg.walk(1, mxn, rt[r], rt[l-1], 0) << "\n";
}
}
