#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 2e5+10;
const int MAXA = 2e5;
const int INF = 1e9+100;
const int SQRT = 500;
const int LOG = 21;
void chmn(auto &a, auto b){ a = min(a, b); }
void chmx(int &a, int b){ a = max(a, b); }
int n, q, a[MAXN];
struct seg {
int l, r, val;
seg *le, *ri;
void bd(int l2, int r2){
l = l2; r = r2; val = 0;
}
void bnc(){
if(le==NULL){
le = new seg(); le->bd(l, md);
}
if(ri==NULL){
ri = new seg(); ri->bd(md+1,r);
}
}
int que(int x, int y){
if(x<=l && r<=y) return val;
if(r<x || y<l) return 0;
bnc();
return le->que(x,y) + ri->que(x,y);
}
seg* upd(int x, int p){
if(r<x || x<l) return this;
if(l==r){
seg *ret; ret = new seg();
*ret = *this;
ret->val += p;
return ret;
}
bnc();
seg *ret; ret = new seg();
*ret = *this;
ret->le = le->upd(x,p);
ret->ri = ri->upd(x,p);
ret->val = ret->le->val + ret->ri->val;
return ret;
}
} *A[MAXN];
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1; i<=n; i++){
cin>>a[i];
}
A[0] = new seg(); A[0]->bd(1,MAXA);
for(int i=1; i<=n; i++){
A[i] = A[i-1]->upd(a[i],1);
// cout << A[i]->que(1,3)<<' '<<A[i]->val <<' '<<a[i]<< " pp\n";
}
for(int i=1; i<=q; i++){
int le, ri; cin>>le>>ri;
// cout << A[ri]->que(1,6)<<' '<<A[le-1]->que(1,6)<< " pp\n";
int l=1, r=MAXA, mid=0, cnt=-1;
while(l<=r){
mid = md;
if(A[ri]->que(mid,MAXA)-A[le-1]->que(mid,MAXA) >= mid)
l = mid+1, cnt = mid;
else r = mid-1;
}
cout << cnt << '\n';
}
}
