/******************************
* author : @marvinthang *
* date : 10 / 02 / 2022 *
******************************/
#include <bits/stdc++.h>
using namespace std;
#define superspeed ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
#define file(name) if (fopen (name".inp", "r")) { freopen (name".inp", "r", stdin); freopen (name".out", "w", stdout); }
template <class U, class V> ostream & operator << (ostream& out, const pair<U, V> &p) { return out << '(' << p.first << ", " << p.second << ')'; }
template <class T> ostream & operator << (ostream &out, const vector<T> &vt) { out << '{'; for (size_t i = 0; i + 1 < vt.size(); i++) out << vt[i] << ", "; if (!vt.empty()) out << vt.back(); return out << '}'; }
const int MOD = 1e9 + 7;
const double PI = 3.1415926535897932384626433832795; // acos(-1.0); atan(-1.0);
const int dir[] = {0, 1, 0, -1, 0}; // {0, 1, 1, -1, -1, 1, 0, -1, 0};
const int MAX = 2e5 + 5;
struct Node {
Node *l, *r;
int val;
Node(Node *_l = nullptr, Node *_r = nullptr, int v = 0) {
l = _l; r = _r; val = v;
}
};
Node *versions[MAX];
const int oo = 1 << 18;
void build(Node *cur, int l = 1, int r = oo - 1) {
if (l == r) return;
int mid = l + r >> 1;
cur -> l = new Node();
build(cur -> l, l, mid);
cur -> r = new Node();
build(cur -> r, mid + 1, r);
}
void upgrade(Node *prev, Node *cur, int pos, int val, int l = 1, int r = oo - 1) {
if (l > pos || r < pos) return;
if (l == r) {
cur -> val = prev -> val + val;
return;
}
int mid = l + r >> 1;
if (pos <= mid) {
cur -> r = prev -> r;
cur -> l = new Node();
upgrade(prev -> l, cur -> l, pos, val, l, mid);
} else {
cur -> l = prev -> l;
cur -> r = new Node();
upgrade(prev -> r, cur -> r, pos, val, mid + 1, r);
}
cur -> val = cur -> l -> val + cur -> r -> val;
}
int get(Node *prev, Node *cur, int u, int l = 1, int r = oo - 1) {
if (l > oo || r < u) return 0;
if (u <= l) return cur -> val - prev -> val;
int mid = l + r >> 1;
return get(prev -> l, cur -> l, u, l, mid) + get(prev -> r, cur -> r, u, mid + 1, r);
}
int N, Q, A[MAX];
int main(void) {
superspeed;
file("coci2021_r6_index");
scanf("%d%d", &N, &Q);
for (int i = 1; i <= N; ++i) scanf("%d", A + i);
versions[0] = new Node();
build(versions[0]);
for (int i = 1; i <= N; ++i) {
versions[i] = new Node();
upgrade(versions[i - 1], versions[i], A[i], 1);
}
while (Q--) {
int l, r; scanf("%d%d", &l, &r);
int low = 1, high = oo;
while (low <= high) {
int mid = low + high >> 1;
if (get(versions[l - 1], versions[r], mid) >= mid)
low = mid + 1;
else high = mid - 1;
}
printf("%d\n", high);
}
return 0;
}
