#include <bits/stdc++.h>
using namespace std;
struct node{
node* l = NULL,* r = NULL;
int sum;
node(node* l, node* r) : l(l), r(r){
sum = (l ? l->sum : 0) + (r ? r->sum : 0);
}
node(int x) : sum(x){}
};
typedef node* pnode;
struct segTree{
vector<pnode> root;
int maxN;
segTree(int n) : maxN(n){
root.push_back(build(0, n));
}
pnode build(int l, int r){
if(l == r-1) return new node(0);
return new node(build(l, (l+r)/2), build((l+r)/2, r));
}
pnode update(pnode t, int poz, int c, int l, int r){
if(l == r-1) return new node(t->sum + c);
int m = (l+r)/2;
if(poz < m) return new node(update(t->l, poz, c, l, m), t->r);
return new node(t->l, update(t->r, poz, c, m, r));
}
void update(int poz, int c){
root.push_back(update(root[root.size()-1], poz, c, 0, maxN));
}
int ask(pnode tl, pnode tr, int ex, int l, int r){
if(l == r-1) return l;
int m = (l+r)/2, sum = tr->r->sum - tl->r->sum;
if(m <= sum+ex) return ask(tl->r, tr->r, ex, m, r);
return ask(tl->l, tr->l, ex + sum, l, m);
}
int ask(int l, int r){
return ask(root[l-1], root[r], 0, 0, maxN);
}
};
int main(){
int n,m;
cin>>n>>m;
vector<int> v(n);
segTree tree = segTree(n);
for(int i = 0; i < n; i++)
cin>>v[i], tree.update(v[i], 1);
while(m--){
int l, r;
cin>>l>>r;
cout<<tree.ask(l, r)<<"\n";
}
}
