#include<bits/stdc++.h>
using namespace std;
const int nMax = 2e5 + 7;
vector < long long > ar;
struct Node{
Node* left;
Node* right;
long long val;
Node(){
left = NULL;
right = NULL;
val = 0;
}
Node(Node* a){
left = a -> left;
right = a -> right;
val = a -> val;
}
};
vector <Node*> roots;
void build(long long l , long long r , Node* nd){
if(l > r){
return;
}
if(l == r){
nd -> val = 0;
return;
}
nd -> right = new Node();
nd -> left = new Node();
long long m = (l + r) / 2;
build(l , m , nd -> left);
build(m + 1 , r , nd -> right);
nd -> val = 0;
}
void update(long long l , long long r , long long f , long long valu , Node* nd){
// cout << l << " " << r;
if(nd == NULL || l > r || l > f || f > r){
return;
}
if(l == r){
nd -> val += valu;
return;
}
long long m = (l + r) / 2;
if(l <= f && f <= m){
nd -> left = new Node(nd -> left);
}
else{
nd -> right = new Node(nd -> right);
}
update(l , m , f , valu , nd -> left);
update(m + 1 , r , f , valu , nd -> right);
nd -> val = (nd -> right -> val) + (nd -> left -> val);
}
long long search(long long l , long long r , long long fl, long long fr , Node* nd){
if(l > r || l > fr || fl > r){
return 0;
}
if(fl <= l && r <= fr){
return nd -> val;
}
long long m = (l + r) / 2;
return search(l , m , fl , fr , nd -> left) + search(m + 1 , r , fl , fr , nd -> right);
}
int main(){
long long n , q , k , x , mx;
mx = 0;
cin >> n >> q;
for(long long i = 1; n >= i; i++){
cin >> x;
mx = max(mx , x);
ar.push_back(x);
}
Node* tmp;
tmp = new Node();
build(1 , mx , tmp);
roots.push_back(tmp);
for(long long i = 1; n >= i; i++){
x = ar[i - 1];
tmp = new Node(roots[i - 1]);
update(1 , mx , x , 1 ,tmp);
roots.push_back(tmp);
}
for(long long i = 0; q > i; i++){
cin >> k >> x;
long long l = 1 , r = mx;
while(r > l){
//cout << l << " " << r <<"\n";
long long m = ((l + r) + 1) / 2;
if((search(1 , mx , m , mx , roots[x]) - search(1 , mx , m , mx , roots[k - 1])) >= m){
l = m;
}
else{
r = m - 1;
}
}
cout << l << "\n";
}
}
