#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK "task"
#define all(x) x.begin(), x.end()
using namespace std;
const int N = 2e5 + 7;
const int MOD = 1e9 + 7; // 998244353;
const int INF = 1e9 + 7;
const long long INFLL = 1e18 + 7;
typedef long long ll;
typedef unsigned long long ull;
template <class X, class Y> bool minimize(X &a, Y b) {
if (a > b) return a = b, true;
return false;
}
template <class X, class Y> bool maximize(X &a, Y b) {
if (a < b) return a = b, true;
return false;
}
struct Node {
int val;
Node *l = NULL, *r = NULL;
Node(int _val = 0) : val(_val) {};
Node(Node *ll, Node *rr) : l(ll), r(rr) {
val = (l ? l->val : 0) + (r ? r->val : 0);
}
};
struct P_IT {
vector<Node*> root;
int n;
P_IT(int _n = 0) : n(_n) {
root.push_back(build(1, n));
}
Node* build(int l, int r) {
if (l == r) return new Node();
int mid = (l + r) >> 1;
return new Node(build(l, mid), build(mid + 1, r));
}
Node* update(Node* node, int pos, int val, int l, int r) {
if (l == r) return new Node(node->val + val);
int mid = (l + r) >> 1;
if (mid < pos) return new Node(node->l, update(node->r, pos, val, mid + 1, r));
return new Node (update(node->l, pos, val, l, mid), node->r);
}
int get(Node* ll, Node* rr, int sum, int l, int r) {
if (l == r) return l;
int mid = (l + r) >> 1, delta = rr->r->val - ll->r->val;
if (mid >= delta + sum) return get(ll->l, rr->l, sum + delta, l, mid);
return get(ll->r, rr->r, sum, mid + 1, r);
}
void update(int pos, int val) {
root.push_back(update(root.back(), pos, val, 1, n));
}
int query(int l, int r) {
return get(root[l - 1], root[r], 0, 1, n);
}
};
void solve(void) {
int n, q; cin >> n >> q;
P_IT st(N);
for (int i = 1; i <= n; i ++) {
int x; cin >> x;
st.update(x, 1);
}
while (q --) {
int l, r; cin >> l >> r;
cout << st.query(l, r) << '\n';
}
}
int main(void) {
cin.tie(0)->sync_with_stdio(0);
int test = 1;
// cin >> test;
while (test --) {
solve();
}
return 0;
}
