#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define int long long
#define PI pair<int,int>
#define f first
#define s second
#define pb push_back
#define szo(x) ((int)x.size())
const int MAX = 2e7;
int seg[MAX];
int L[MAX], R[MAX];
int nodes = 1;
const int LIM = 2e5+10;
void build(int x = 1, int l = 0, int r = LIM){
if (l == r) return;
int tm = (l+r)/2;
L[x] = nodes++, R[x] = nodes++;
build(L[x], l, tm); build(R[x], tm+1, r);
}
int update(int id, int val, int x, int xo, int l = 0, int r = LIM){
if (l == r) return seg[x] = seg[xo]+val;
int tm = (l+r)/2;
if (id <= tm) return seg[x] = update(id, val, L[x] = nodes++, L[xo], l, tm) + seg[R[x] = R[xo]];
return seg[x] = update(id, val, R[x] = nodes++, R[xo], tm+1, r) + seg[L[x] = L[xo]];
}
int solve(int r1, int r2, int acc, int l = 0, int r = LIM){
if (l == r) return l;
int tm = (l+r)/2;
if (acc + seg[R[r1]] - seg[R[r2]] >= tm+1) return solve(R[r1], R[r2], acc, tm+1, r);
return solve(L[r1], L[r2], acc+seg[R[r1]]-seg[R[r2]], l, tm);
}
int32_t main(){
ios_base::sync_with_stdio(false); cin.tie(0);
int n,q; cin >> n >> q;
vector<int> vec(n+1);
for (int i = 1; i <= n; ++i) cin >> vec[i];
build();
vector<int> rts(n+1);
rts[0] = 0;
for (int i = 1; i <= n; ++i){
rts[i] = nodes++;
update(vec[i], 1, rts[i], rts[i-1]);
}
while (q--){
int l, r; cin >> l >> r;
cout << solve(rts[r], rts[l-1], 0) << '\n';
}
return 0;
}
