#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define umap unordered_map
#define prq priority_queue
#define vect vector
#define rs resize
#define bend(v) v.begin(),v.end()
#define pob pop_back
#define pof pop_front
#define lwb lower_bound
#define upb upper_bound
#define pii pair<int,int>
#define nextl cout << '\n'
#define el '\n'
#define deb cout<<"\nok\n";return
#define ll long long
#define dbl long double
#define popcnt __builtin_popcount
#define ctz __builtin_ctz
#define FILE "ellencute"
const ll INF=902337203695775807, N=2e5+69, MOD=1e9+7;
void ffopen(){
if(fopen(FILE".inp", "r")){
freopen(FILE".inp", "r", stdin);
freopen(FILE".out", "w", stdout);
}else if(fopen("ellencute.inp", "r")){
freopen("ellencute.inp", "r", stdin);
freopen("ellencute.out", "w", stdout);
}
}
int pm(int a,const int b=1e9+7){return ((a%b)+b)%b;}
int sq(int x){return x*x;}
ll __lcm(ll a, ll b, const ll lim=LLONG_MAX){
if(a == -1 || b == -1)return -1;
ll g = __gcd(a,b);
if(b/g > lim/a)return -1;
return (a/g)*b;
}
int t[4*N], lz[4*N];
struct Seggs{
Seggs(){build();}
void build(int l=1, int r=2e5, int id=1){
if(l == r){
t[id] = -l;
return;
}
int mid = (l+r)/2;
build(l, mid, id*2);
build(mid+1, r, id*2+1);
t[id] = max(t[id*2], t[id*2+1]);
}
void push(int l, int r, int id, bool b=0){
t[id] += lz[id];
if(l < r){
lz[id*2] += lz[id];
lz[id*2+1] += lz[id];
if(b){
int mid = (l+r)/2;
push(l, mid, id*2);
push(mid+1, r, id*2+1);
t[id] = max(t[id*2], t[id*2+1]);
}
}
lz[id] = 0;
}
void upd(int p, int x, int l=1, int r=2e5, int id=1){
if(l > p)return;
if(r <= p){
// cout << l << ' ' << r << el;
lz[id]+=x;
push(l, r, id);
return;
}
int mid = (l+r)/2;
upd(p, x, l, mid, id*2);
upd(p, x, mid+1, r, id*2+1);
t[id] = max(t[id*2], t[id*2+1]);
// if(p==3 && x==1 && id==1){
// cout << t[id] << el;
// }
}
int get(int l=1, int r=2e5, int id=1){
push(l, r, id, 1);
// cout << l << ' ' << r << ' '<< t[id] << el;
if(l == r)return l;
int mid = (l+r)/2;
if(t[id*2+1]>=0)return get(mid+1, r, id*2+1);
return get(l, mid, id*2);
}
} sgt;
struct query{
int l, r, id;
};
void sol(){
int n, q;
cin >> n >> q;
int a[n], ans[q];
for(int& i : a)cin >> i;
query que[q];
for(int i=0;q>i;i++){
cin >> que[i].l >> que[i].r;
que[i].l--;que[i].r--;
que[i].id=i;
}
const int S = sqrt(n / log2(n));
sort(que, que+q, [&](const query& a, const query& b){
if(a.l/S != b.l/S)return a.l < b.l;
if(a.l/S & 1)return a.r < b.r;
return a.r > b.r;
});
int l=0, r=-1;
for(auto [L, R, id] : que){
// cout << sgt.get() << el;
while(r<R)sgt.upd(a[++r], 1);
while(l>L)sgt.upd(a[--l], 1);
// cout << sgt.get() << el;
while(r>R)sgt.upd(a[r--], -1);
while(l<L)sgt.upd(a[l++], -1);
ans[id] = sgt.get();
}
for(int i : ans)cout << i << el;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ffopen();
int t=1;
//cin >> t;
while(t--)sol();
}
/*
...-%%%%%%%%%%%...
.:**#%=%%%%%+........-%%%%. .
.%%%%%%=-..%#. .#%%.
%%%+.. .: *%%.
.%%. :. :%%%%%:.
.%%. ... .: :: .=%%%.
..%%. #%#:%. : :.. =%%.
%%+..: .%*::::%-::::::-::::::.. .:-%%%%. .*%%..
.%# :.%:::::::%%%%%%%%%%%%%+...%%%+::::%#. .%%.
.%%. ..:.%=::::*%#***#%::::::::%%%%=:::::::%%. .%%.
=%%%...-%%%:::*%********%:::%%%****%::::::::%% .%-
.%::::%%***%=:%%**********%%********%:::::::=%-:. .%..
#%:::%#*****%%**********************%:::+%%%*%%-.: .::..%%.
.%%::%%*****==**==*****#************#%%%%#******%%..::::.. .%%.
.%%#%+%%***************##*+=+*==********************%%.:. .%%
.%%***%%****************#**==**==******==**+=+********%%%%%%%%% %%.
.#%#*********************%%**************++************%%::::::%* .%%%.
.%%***************#*****%%%****************************%%::::::%% .-%%%.
.#%***************#****%%--%*********%*****************%#::::-%%%%%%%%%%.
.%%**************#**%%%----%********%%**************#***#%%%#**%#******%*
.%%**************#%%%--.....%%*******%%**************#**********#%******%%.
.%%*************%%...........%%******%-%*************#***********%%*****%%.
.%%*************%%...%%%%%.....%%%%%%%.=%%%%%%%%##****#****##::::+%%*****%#
.%%************%%...%. %%.................%%%%-.....%*****#*****%%*****%%
.#%#*#****#****%%:::%- %%.................%. #-....%*****#*#####%#****%%.
.%%##****%%%**%%:::::##...................%= .%+:::%#*****#:####*%%****%%.
.+%%#**%%.#%%%%::::::........###+.:*##-....%%%:::::%*****##******%%****%%-
..%%*%%.......:::.......##..#*...#+..#*....:::::%******#*****##%%*****%%.
.%%%%%................#-##=--##+-+###-#....:::%******#:###*::%%#*****%%.
.%%****%%..............#----------------=*...#%#****##**##::#**%%*******%%.
.%%%%%*=+%%*...........#-----------------#.....#%%%%%%+:##*##:*%%*******%%%.
..:*%====%%%%........#-----------------#:.........%#********%%*****%%%%%%.
.%%=======*%%%%%%%.%%+----#-%------%%#.......%%%%::::::::%%==***#%###%%.
..%%=============+%%-:#%%%%-::%%%%%%::%%%%%%%%%=%%*******%%=====**%%###%%..
-%%%%%%%%%%%%%%%%+%.%+:+%::%::::%::%:::%%#%... .%%******%%%========#%####%%.
.%%++#############%%# ..%%.**%%#%%%%%%%#%***%. :%%*****%%%=+%%%%%%%%%%#####%%.
.%%++++*############*++% .%************#****%. #%*%%%%+++%%%%###############%%.
.+%%%%%%%%%%####+##########*+++++%%. .%**#**********#****% %%**%%%++++###################%:
=%%%%######################++++++++%%*%.-%%#***********#****% .%****%%+++++###################%%
.%%%#######################*%%%%%%%%.%%*#%+%###################%.%%***%%%+++++###################%%
*%%######################+#%%++++++%*. =%*%. .:%%%%########%%%%%%%%%#*#%.%%++#####################%%
.%%%#####################%%%%%+++++++%- %*#%%. .%%%*++++++*%%%....%%#####################%%*
%%######%%%%%#%%%%%######%%.%*+++++++%. %****#. .%%+++*+++++*++%%...=%%###################%%%.
%%%%%%%%#-=##%...%%######%%.%%+++++++%%..*%***#%%%%%. ..%+++++++++++++++%%...%%##################%%%.
.%:. .#%#####%%.%%+++++++++%. %*********%%%%%++++++++++++++++%%...%%##############%%%%..
:%#####%% .%%+++++++%% .%%**********%%++++++++++++++++%%.....%#########%%%%%% .
*%#####%%. .%%+++++++%%:. .%%********%%++++++++++++++++%%....%%%%%%%%%%%%*..
.%%##%%% .%%*+++++++%%. ..#%%%#****%%+++++++++++++++%%%%%% . .....
%%#%%%. .:%%%%%%%%%%%...-%. ......%%+++++++++++++%%.
..%%%. ... .%%%#%%%=:#%%%%%%%%*++++++%%%#
.-%%+. ... .%%%%%%%:.
*/
