#include <bits/stdc++.h>
using namespace std;
#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define int long long
typedef long long ll;
typedef pair<int,int> ii;
const int INF = 0x3f3f3f3f3f3f3f3fll;
const int MAX = 2e5 + 10;
struct Vertex {
Vertex *l, *r;
int sum;
Vertex(int v) : l(nullptr), r(nullptr), sum(v) {}
Vertex(Vertex *l, Vertex *r) : l(l), r(r), sum(0) {
if(l) sum += l->sum;
if(r) sum += r->sum;
}
};
Vertex* build(int begin = 0, int end = MAX) {
if(begin == end) return new Vertex(0);
int m = (begin + end) >> 1;
return new Vertex(build(begin, m), build(m + 1, end));
}
Vertex* update(Vertex* v, int index, int add, int begin = 0, int end = MAX) {
if(begin == end) return new Vertex(v->sum + add);
int m = (begin + end) >> 1;
if(index <= m) return new Vertex(update(v->l, index, add, begin, m), v->r);
else return new Vertex(v->l, update(v->r, index, add, m + 1, end));
}
int query(Vertex* vl, Vertex *vr, int suffix, int begin = 0, int end = MAX) {
if(begin == end) return begin;
int right = vr->r->sum - vl->r->sum + suffix;
int m = (begin + end) >> 1;
if(right > m) return query(vl->r, vr->r, suffix, m + 1, end);
return query(vl->l, vr->l, right, begin, m);
}
int32_t main() { _
int n, q; cin >> n >> q;
vector<int> p(n);
for(int & i : p) cin >> i;
vector<Vertex*> roots;
roots.push_back(build());
for(int i = 0; i < n; i++) {
roots.push_back(update(roots.back(), p[i], 1));
}
while(q--) {
int l, r; cin >> l >> r;
cout << query(roots[l-1], roots[r], 0) << endl;
}
return 0;
}
