#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
const int mxN=2e5;
int n, q, a[mxN];
struct Node {
int sum=0;
Node *left=nullptr, *right=nullptr;
Node(int l, int r) {
if (l!=r) {
int mid=(l+r)/2;
left=new Node(l, mid);
right=new Node(mid+1, r);
}
}
Node(int x) : sum(x) {}
Node(Node* l, Node* r) {
assert(l&&r);
sum=l->sum+r->sum;
left=l;
right=r;
}
Node* upd(int i, int l=1, int r=mxN) {
if (l>i||r<i)
return this;
if (l==r)
return new Node(sum+1);
int mid=(l+r)/2;
return new Node(left->upd(i, l, mid), right->upd(i, mid+1, r));
}
};
vector<Node*> roots;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> q;
roots.push_back(new Node(1, mxN));
for (int i=0; i<n; ++i) {
cin >> a[i];
roots.push_back(roots.back()->upd(a[i]));
}
while(q--) {
int ql, qr;
cin >> ql >> qr, --ql, --qr;
Node *u=roots[ql], *v=roots[qr+1];
int l=1, r=mxN, extra=0;
while(l<r) {
int mid=(l+r)/2;
int cnt=(v->right->sum)-(u->right->sum);
if (cnt+extra>=mid+1) {
l=mid+1;
u=u->right, v=v->right;
} else {
r=mid, extra+=cnt;
u=u->left, v=v->left;
}
}
cout << l << "\n";
}
return 0;
}
