#include <iostream>
#include <math.h>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <cstring>
#include <iomanip>
#include <set>
#include <bitset>
#include <unordered_map>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using piii = tuple<int,int,int>;
#define f first
#define s second
#define endl '\n'
#define all(x) begin(x),end(x)
#define m_p make_pair
struct Node{
int val;
Node* l;
Node* r;
Node() : val(0),l(0),r(0) {}
};
typedef Node* pnode;
void builder(pnode &node,int l,int r){
node = new Node();
if(l != r){
int md = l+(r-l)/2;
builder(node->l,l,md);
builder(node->r,md+1,r);
}
}
void update(pnode &node,pnode time,int l,int r,int idx,int val){
node = new Node(*time);
if(l == r && l == idx) node->val += val;
else if(l > idx || r < idx) return;
else{
int md = l+(r-l)/2;
if(idx <= md) update(node->l,time->l,l,md,idx,val);
else update(node->r,time->r,md+1,r,idx,val);
node->val = node->l->val+node->r->val;
}
}
int query(pnode L,pnode R,int l,int r,int ql,int qr){
if(l >= ql && r <= qr) return R->val-L->val;
else if(l > qr || r < ql) return 0;
else{
int md = l+(r-l)/2;
int q1 = query(L->l,R->l,l,md,ql,qr);
int q2 = query(L->r,R->r,md+1,r,ql,qr);
return q1+q2;
}
}
vector<pnode> tree = {nullptr};
int main(){
int n;cin >> n;
int q;cin >> q;
builder(tree.back(),1,n);
for(int i{};i < n;i++){
int g;cin >> g;
tree.emplace_back(nullptr);
update(tree.back(),tree[tree.size()-2],1,n,g,1);
}
for(int i{};i < q;i++){
int a,b;cin >> a >> b;
a--;
int l = 1;
int r = n;
// for(int i{1};i <= n;i++){
// cout << query(tree[a],tree[b],1,n,i,i) << " ";
// }
// cout << endl;
while(l < r){
int md = l+(r-l-1)/2;
if(query(tree[a],tree[b],1,n,md,n) < md) r = md;
else l = md+1;
}
cout << l-1 << endl;
}
}
