#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MAXC = 10000000;
const int MAXN = 200000;
struct Segment{
int L, R, val;
} seg[MAXC];
int idxx;
void init(int node, int l, int r){
if(l == r) return;
int mid = (l+r)/2;
seg[node].L = ++idxx;
seg[node].R = ++idxx;
init(seg[node].L, l, mid);
init(seg[node].R, mid+1, r);
}
void upd(int node, int pnode, int l, int r, int x){
if(l == r){
seg[node].val = seg[pnode].val + 1;
return;
}
int mid = (l+r)/2;
seg[node].L = seg[pnode].L;
seg[node].R = seg[pnode].R;
if(x <= mid){
seg[node].L = ++idxx;
upd(seg[node].L, seg[pnode].L, l, mid, x);
}
else{
seg[node].R = ++idxx;
upd(seg[node].R, seg[pnode].R, mid+1, r, x);
}
seg[node].val = seg[seg[node].L].val + seg[seg[node].R].val;
}
int root[MAXN+5];
int query(int node, int pnode, int l, int r, int ost){
if(l == r) return l;
int mid = (l+r)/2;
if(seg[seg[node].R].val - seg[seg[pnode].R].val + ost >= mid+1) return query(seg[node].R, seg[pnode].R, mid+1, r, ost);
return query(seg[node].L, seg[pnode].L, l, mid, ost + seg[seg[node].R].val - seg[seg[pnode].R].val);
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, qrs;
cin >> n >> qrs;
idxx = 1;
root[0] = 1;
init(1, 1, n);
for(int i=1; i<=n; i++){
int x;
cin >> x;
root[i] = root[i-1];
int old = root[i];
root[i] = ++idxx;
upd(root[i], old, 1, n, x);
}
while(qrs--){
int l, r;
cin >> l >> r;
cout << query(root[r], root[l-1], 1, n, 0) << "\n";
}
return 0;
}
