#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
// https://codeforces.com/blog/entry/79148
class Timer: chrono::high_resolution_clock {
const time_point start_time;
public:
Timer(): start_time(now()) {}
rep elapsed_time() const {
return chrono::duration_cast<chrono::milliseconds>(now() - start_time).count();
}
} timer;
struct FenwickTree {
int n;
vector<int> tree;
FenwickTree(int n_) {
n = n_;
tree.resize(n + 1, 0);
}
void update(int p) {
while (p <= n) {
tree[p]++;
p += p & (-p);
}
}
int prefixQuery(int r) {
int res = 0;
while (r) {
res += tree[r];
r -= r & (-r);
}
return res;
}
int query(int l, int r) {
return prefixQuery(r) - prefixQuery(l - 1);
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<vector<int>> pos(2e5 + 1);
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
pos[x].push_back(i);
}
vector<pair<int, int>> queries(q);
for (int i = 0; i < q; i++) {
cin >> queries[i].first >> queries[i].second;
}
queue<tuple<int, int, vector<int>>> bs;
vector<int> init(q), ans(q, 0), all, nxt(2e5, 0), pr(2e5);
for (int i = 2e5; i; i--) {
if (pos[i].size()) {
all.push_back(i);
}
}
for (int i = 0; i < all.size() - 1; i++) {
nxt[all[i]] = all[i + 1];
}
for (int i = 1; i < all.size(); i++) {
pr[all[i]] = all[i - 1];
}
pr[all[0]] = 1e9;
pr[0] = all.back();
iota(init.begin(), init.end(), 0);
bs.push({1, 2e5, init});
int cur = all[0];
FenwickTree fwt(n);
while (bs.size()) {
auto [l, r, v] = bs.front();
bs.pop();
if (r - l <= 2) {
if (pr[cur] < r) {
fwt = FenwickTree(n);
cur = all[0];
}
while (cur >= r) {
for (auto &i : pos[cur]) {
fwt.update(i);
}
cur = nxt[cur];
}
for (auto &i : v) {
auto &[lb, rb] = queries[i];
if (fwt.query(lb, rb) >= r) {
ans[i] = max(ans[i], r);
}
}
while (cur >= l + 1) {
for (auto &i : pos[cur]) {
fwt.update(i);
}
cur = nxt[cur];
}
for (auto &i : v) {
auto &[lb, rb] = queries[i];
if (fwt.query(lb, rb) >= l + 1) {
ans[i] = max(ans[i], l + 1);
}
}
while (cur >= l) {
for (auto &i : pos[cur]) {
fwt.update(i);
}
cur = nxt[cur];
}
for (auto &i : v) {
auto &[lb, rb] = queries[i];
if (fwt.query(lb, rb) >= l) {
ans[i] = max(ans[i], l);
}
}
}
else {
int m = (l + r) / 2;
if (pr[cur] < m) {
fwt = FenwickTree(n);
cur = all[0];
}
while (cur >= m) {
for (auto &i : pos[cur]) {
fwt.update(i);
}
cur = nxt[cur];
}
vector<int> vl, vr;
for (auto &i : v) {
auto &[lb, rb] = queries[i];
if (fwt.query(lb, rb) >= m) {
vr.push_back(i);
}
else {
vl.push_back(i);
}
}
bs.push({m, r, vr});
bs.push({l, m - 1, vl});
}
}
for (auto &i : ans) {
cout << i << "\n";
}
return 0;
}
