#include <bits/stdc++.h>
#define f first
#define s second
#define ll long long
#define pii pair<int, int>
using namespace std;
struct node {
int val, left_idx, right_idx;
node *l, *r;
node(int val, int left_idx=0, int right_idx=0, node *l=NULL, node *r=NULL) :
val(val), left_idx(left_idx), right_idx(right_idx), l(l), r(r) {}
};
int n, w;
int p[200002];
node *seg[200002];
node* build(int l, int r) {
if (l == r) return new node(0, l, l);
int mid = (l + r) >> 1;
node *resl = build(l, mid);
node *resr = build(mid+1, r);
return new node(
resl->val + resr->val,
resl->left_idx,
resr->right_idx,
resl,
resr
);
}
void upgrade(node *pre, node *cur, int i, int val, int l, int r) {
if (l == r) {
cur->val = pre->val + val;
cur->left_idx = l;
cur->right_idx = l;
return;
}
int mid = (l + r) >> 1;
if (i <= mid) {
cur->l = new node(0);
cur->r = pre->r;
upgrade(pre->l, cur->l, i, val, l, mid);
} else {
cur->l = pre->l;
cur->r = new node(0);
upgrade(pre->r, cur->r, i, val, mid+1, r);
}
cur->val = cur->l->val + cur->r->val;
cur->left_idx = cur->l->left_idx;
cur->right_idx = cur->r->right_idx;
}
int findd(node *right, node *left, int add, int l, int r) {
if (l == r) {
return l;
}
int mid = (l + r) >> 1;
int val = right->r->val - left->r->val + add;
int left_idx = right->r->left_idx;
if (left_idx <= val) {
return findd(right->r, left->r, add, mid+1, r);
} else {
return findd(right->l, left->l, val, l, mid);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> w;
for (int i = 1; i <= n; i++) cin >> p[i];
seg[0] = build(1, 200000);
// cout << seg[0]->r->left_idx << " " << seg[0]->l->right_idx << "\n";
for (int i = 1; i <= n; i++) {
seg[i] = new node(0);
upgrade(seg[i-1], seg[i], p[i], 1, 1, 200000);
}
// cout << "hello\n";
// return 0;
int l, r;
while (w--) {
cin >> l >> r;
int ans = findd(seg[r], seg[l-1], 0, 1, 200000);
// for (auto it : res) cout << it << " "; cout << "\n";
cout << ans << "\n";
}
return 0;
}
