#include <bits/stdc++.h>
#define ub(x) (x&(-x))
using namespace std;
constexpr int NMAX = 2e5 + 5;
int Bucket;
struct intrebare {
int L, R;
int ind;
bool operator < (const intrebare &other) const {
return (L / Bucket < other.L / Bucket) || (L / Bucket == other.L / Bucket && R < other.R);
}
};
intrebare quer[NMAX];
int N, Q;
int aib[NMAX];
int A[NMAX];
void Update (int pos, int val) {
for (int i = pos; i <= N; i += ub(i))
aib[i] += val;
}
int Query (int pos) {
int S = 0;
for (int i = pos; i; i -= ub(i))
S += aib[i];
return S;
}
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q;
Bucket = Q / sqrt(N);
for (int i = 1; i <= N; ++ i )
cin >> A[i];
for (int i = 1; i <= Q; ++ i ) {
cin >> quer[i].L >> quer[i].R;
quer[i].ind = i;
}
sort(quer+1, quer+Q+1);
}
int sol[NMAX];
void Add (int pos) {
Update(A[pos], +1);
}
void Elimin (int pos) {
Update(A[pos], -1);
}
int Raspuns (int Total) {
int st = 1, dr = N;
int ans = 1;
while (st <= dr) {
int mij = (st + dr) / 2;
int cnt = Query(mij-1);
if (Total - cnt >= mij) {
st = mij + 1;
ans = mij;
}
else dr = mij - 1;
}
return ans;
}
/*
dp[i][j] - i cifre cu ultimele 4 cifre j
dp[i][j] = max(dp[i-1][jprim]) + 1 (j este lucky)
i cifre : a b c m
i-1 cifre: n a b c
dp[i][j][k][l][m] = max(dp[i-1][aux][j][k][l]) + 1
*/
void Solve () {
int st = 1, dr = 0;
for (int i = 1; i <= Q; ++ i ) {
while (dr < quer[i].R) {
++ dr;
Add(dr);
}
while (st > quer[i].L) {
-- st;
Add(st);
}
while (st < quer[i].L) {
Elimin(st);
++ st;
}
while (dr > quer[i].R) {
Elimin(dr);
-- dr;
}
sol[quer[i].ind] = Raspuns(quer[i].R - quer[i].L + 1);
}
for (int i = 1; i <= Q; ++ i )
cout << sol[i] << '\n';
}
int main () {
Read();
Solve();
return 0;
}
