#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second
#define pb push_back
#define ep emplace
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniquev(v) sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define mem(f,x) memset(f , x , sizeof(f))
#define sz(x) (int)(x).size()
#define __lcm(a, b) (1ll * ((a) / __gcd((a), (b))) * (b))
#define mxx *max_element
#define mnn *min_element
#define cntbit(x) __builtin_popcountll(x)
#define len(x) (int)(x.length())
const int N = 1e6 + 100;
const int lim = 2e5 + 100;
struct node{
ll s = 0;
node * l, *r;
node() {};
node(node *L, node *R, ll v) {
l = L;
r = R;
s = v;
}
};
node *seg[N];
void build(node *root, int l, int r) {
if (l == r) {
return;
}
int m = (l + r) / 2;
root -> l = new node(NULL, NULL, 0);
root -> r = new node(NULL, NULL, 0);
build(root -> l, l, m);
build(root -> r, m + 1, r);
}
void upd(node *pr, node *cur, int l, int r, int v) {
if (l > v || r < v)
return;
if (l == r) {
return;
}
int m = (l + r) / 2;
if (v <= m) {
cur -> r = pr -> r;
cur -> l = new node(NULL, NULL, pr -> l -> s + 1);
upd(pr -> l, cur -> l, l, m, v);
} else {
cur -> l = pr -> l;
cur -> r = new node(NULL, NULL, pr -> r -> s + 1);
upd(pr -> r, cur -> r, m + 1, r, v);
}
}
ll get(node *root, int l, int r, int u, int v) {
if (l > v || r < u)
return 0;
if (l >= u && r <= v) {
return root -> s;
}
int m = (l + r) / 2;
return get(root -> l, l, m, u, v) + get(root -> r, m + 1, r, u, v);
}
ll a[N];
ll solve() {
int n, q;
cin >> n >> q;
seg[0] = new node(NULL, NULL, 0);
build(seg[0], 1, lim);
for (int i = 1; i <= n; i++) {
cin >> a[i];
seg[i] = new node(NULL, NULL, seg[i - 1] -> s + 1);
upd(seg[i - 1], seg[i], 1, lim, a[i]);
}
while (q--) {
int u, v;
cin >> u >> v;
int l = 1, r = lim, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
if (get(seg[v], 1, lim, m, lim) - get(seg[u - 1], 1, lim, m, lim) >= m) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
cout << ans << '\n';
}
return 0;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t = 1;
//cin >> t;
while (t--) {
solve();
//cout << solve() << '\n';
}
}
