#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
typedef long long ll;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;
const int MAX = 2e5 + 10;
const int UPD = 2e5 + 10;
const int LOG = 18;
const int MAXS = 2 * MAX + UPD * LOG;
int cnt;
int seg[MAXS], L[MAXS], R[MAXS];
void build(int p, int l=0, int r=MAX-1){
if(l == r) return void();
L[p] = cnt++, R[p] = cnt++;
int m = (l+r)/2;
build(L[p], l, m); build(R[p], m+1, r);
}
void update(int i, int x, int np, int p, int l=0, int r=MAX-1){
if(l == r) return void(seg[np] = seg[p] + x);
int m = (l+r)/2;
if(i <= m){
L[np] = cnt++;
R[np] = R[p];
update(i, x, L[np], L[p], l, m);
}
else{
L[np] = L[p];
R[np] = cnt++;
update(i, x, R[np], R[p], m+1, r);
}
seg[np] = seg[L[np]] + seg[R[np]];
}
int solve(int lp, int rp, int sum=0, int l=0, int r=MAX-1){
if(seg[rp] - seg[lp] + sum < l) return -1;
if(l == r) return l;
int m = (l+r)/2;
int x = solve(R[lp], R[rp], sum, m+1, r);
if(x != -1) return x;
sum += seg[R[rp]] - seg[R[lp]];
return solve(L[lp], L[rp], sum, l, m);
}
int main() { _
int n, q; cin >> n >> q;
vector<int> a(n+1); for(int i=1; i<=n; i++) cin >> a[i];
vector<int> vers(n+1);
cnt = 1;
build(0);
vers[0] = 0;
for(int i=1; i<=n; i++){
int rt = cnt++;
update(a[i], +1, rt, vers[i-1]);
vers[i] = rt;
}
while(q--){
int l, r; cin >> l >> r;
cout << solve(vers[l-1], vers[r]) << endl;
}
exit(0);
}
