#define taskname ""
#include <bits/stdc++.h>
using namespace std;
const int kMaxN = 200005;
const int kMaxAi = 200005;
const int kMaxLog = 19;
int n, q, p[kMaxN], root[kMaxN];
struct PersistentSegmentTree {
struct Node {
int left_child = 0, right_child = 0;
int sum = 0;
};
vector<Node> st;
int total_nodes = 0;
PersistentSegmentTree() {}
PersistentSegmentTree(int sz) {
st.resize(sz + 1);
}
int NewNode(int m) {
st[++total_nodes] = st[m];
return total_nodes;
}
int Update(int node_id, int l, int r, int pos, int val) {
node_id = NewNode(node_id);
if (l == r) {
st[node_id].sum += val;
} else {
int mid = (l + r) / 2;
if (pos <= mid) {
st[node_id].left_child = Update(st[node_id].left_child, l, mid, pos, val);
} else {
st[node_id].right_child = Update(st[node_id].right_child, mid + 1, r, pos, val);
}
st[node_id].sum = st[st[node_id].left_child].sum + st[st[node_id].right_child].sum;
}
return node_id;
}
int Query(int node_id, int l, int r, int ql, int qr) {
if (qr < l || ql > r) {
return 0;
}
if (ql <= l && r <= qr) {
return st[node_id].sum;
}
int mid = (l + r) / 2;
return Query(st[node_id].left_child, l, mid, ql, qr) + Query(st[node_id].right_child, mid + 1, r, ql, qr);
}
} tree;
int main() {
if (fopen(taskname".inp", "r")) {
freopen(taskname".inp", "r", stdin);
freopen(taskname".out", "w", stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
tree = PersistentSegmentTree(kMaxLog * kMaxAi);
for (int i = 1; i <= n; i++) {
root[i] = tree.Update(root[i - 1], 1, kMaxAi, p[i], 1);
}
while (q--) {
int l, r;
cin >> l >> r;
int low = 1, high = kMaxAi, result;
while (low <= high) {
int mid = (low + high) / 2;
if (tree.Query(root[r], 1, kMaxAi, mid, kMaxAi) - tree.Query(root[l - 1], 1, kMaxAi, mid, kMaxAi) >= mid) {
result = mid, low = mid + 1;
} else {
high = mid - 1;
}
}
cout << result << '\n';
}
return 0;
}
