#include <bits/stdc++.h>
#define DEBUG 0
using namespace std;
const int N = 2e5 + 10;
int p[N];
vector <int> idx_paper[N];
class Node {
public :
int sum;
Node *l, *r;
Node(int s) : sum(s), l(NULL), r(NULL) {}
Node(Node *L, Node *R) : sum(0), l(L), r(R) {
if(L != NULL) {
sum += L->sum;
}
if(R != NULL) {
sum += R->sum;
}
}
Node(Node *copy) : sum(copy->sum), l(copy->l), r(copy->r) {}
};
Node *root[N];
Node *build(int l, int r) {
if(l == r) {
return new Node(0);
}
int mid = (l + r) / 2;
return new Node(build(l, mid), build(mid + 1, r));
}
Node *update(Node *node, int l, int r, int q) {
if(l == r) {
return new Node(1);
}
int mid = (l + r) / 2;
if(q <= mid) {
return new Node(update(node->l, l, mid, q), node->r);
}
return new Node(node->l, update(node->r, mid + 1, r, q));
}
int query(Node *node, int l, int r, int ql, int qr) {
if(r < ql or qr < l) {
return 0;
}
if(ql <= l and r <= qr) {
return node->sum;
}
int mid = (l + r) / 2;
return query(node->l, l, mid, ql, qr) + query(node->r, mid + 1, r, ql, qr);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
for(int i = 1; i <= n; i++) {
cin >> p[i];
idx_paper[p[i]].push_back(i);
}
root[n + 1] = build(1, n);
for(int i = n; i >= 1; i--) {
root[i] = new Node(root[i + 1]);
for(auto idx : idx_paper[i]) {
root[i] = update(root[i], 1, n, idx);
}
}
while(q--) {
int a, b;
cin >> a >> b;
int range = b - a + 1;
int l = 1, r = range, pos = 1;
while(l <= r) {
int mid = (l + r) / 2;
if(query(root[mid], 1, n, a, b) < mid) {
r = mid - 1;
}
else {
l = mid + 1;
pos = mid;
}
}
cout << pos << '\n';
}
return 0;
}
