#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 10;
int n, q;
int ans[N], BIT[N], h[N];
vector <int> p[N];
struct dta {
int L, R, i;
};
void add(int i, int delta) {
for (; i <= n; i += i & - i) BIT[i] += delta;
}
int get(int i) {
int ans = 0;
for (; i; i -= i & - i) ans += BIT[i];
return ans;
}
void solve(int L, int R, vector <dta>& task) {
if (task.empty()) return;
if (L == R) {
for (auto [u, v, i]: task) ans[i] = L;
return;
}
int mid = L + R >> 1;
for (int i = R; i > mid; --i)
for (auto id: p[i]) add(id, 1);
vector <dta> p1, p2;
for (auto [u, v, i]: task) {
if (get(v) - get(u - 1) >= mid + 1) p2.push_back({u, v, i});
else p1.push_back({u, v, i});
}
solve(L, mid, p1);
for (int i = R; i > mid; --i)
for (auto id: p[i]) add(id, -1);
solve(mid + 1, R, p2);
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
cin >> n >> q;
for (int i = 1; i <= n; ++i) cin >> h[i];
for (int i = 1; i <= n; ++i) p[h[i]].push_back(i);
vector <dta> task;
for (int i = 1; i <= q; ++i) {
int L, R;
cin >> L >> R;
task.push_back({L, R, i});
}
solve(0, n, task);
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
