#include <bits/stdc++.h>
#define int long long
#define F first
#define S second
#define pii pair<int,int>
const int mod = 1e9 + 7;
const int mxN = (1 << 22) + 1;
using namespace std;
struct node{
node *l,*r;
int val;
node(): l(0), r(0), val(0){}
node(node* L, node* R, int V): l(L), r(R), val(V){}
};
int N;
vector<node*>root;
int query(int l, int r, int s,int e, node* cur){
if(l > e || r < s) return 0;
if(l >= s && r <= e) return cur->val;
int op1 = 0,op2 = 0;
int md = (l + r) / 2;
if(cur->l != 0) op1 = query(l,md,s,e,cur->l);
if(cur->r != 0) op2 = query(md + 1,r,s,e,cur->r);
return op1 + op2;
}
node* update(int l,int r,int ind,int val, node* cur){
if(l == r) return new node(cur->l,cur->r,cur->val + val);
int md = (l + r) / 2;
node *L = new node;
node *R = new node;
if(ind <= md) {
L = update(l,md,ind,val,cur->l);
R = cur->r;
}else{
L = cur->l;
R = update(md + 1,r,ind,val,cur->r);
}
return new node(L,R,L->val + R->val);
}
node* build(int l,int r){
if(l == r) return new node(nullptr,nullptr,0);
node *cur = new node();
int md = (l + r) / 2;
cur->l = build(l,md);
cur->r = build(md + 1,r);
return cur;
}
int walk(int l,int r,node* st, node* ed){
if(l == r) return l;
int md = (l + r) / 2;
// cout<<l<<' '<<r<<' '<<query(1,N,md + 1,N,ed)<<' '<<query(1,N,md + 1,N,st)<<'\n';
if(query(1,N,md + 1,N,ed) - query(1,N,md + 1,N,st) >= md + 1) return walk(md + 1,r,st,ed);
return walk(l,md,st,ed);
}
void printseg(node* cur){
int cnt = 0;
int ex = 1;
queue<node*>q;
q.push(cur);
while(q.size()){
cnt++;
auto u = q.front();
q.pop();
cout<<u->val<<' ';
if(ex * 2 - 1 == cnt){
cout<<'\n';
ex *= 2;
}
if(u->l != 0) q.push(u->l);
if(u->r != 0) q.push(u->r);
}
}
signed main(){
int n,q;
cin >>n>>q;
N = exp2(ceil(log2(n)));
root.push_back(build(1,N));
for(int i = 1;i <= n;i++){
int x;
cin >>x;
root.push_back(update(1,N,x,1,root.back()));
}
// for(auto x : root){
// printseg(x);
// cout<<'\n';
// }
while(q--){
int x,y;
cin >>x>>y;
// printseg(root[x - 1]);
// cout<<'\n';
// printseg(root[y]);
// cout<<'\n';
cout<<walk(1,N,root[x - 1],root[y])<<'\n';
}
}
