#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pll pair<long long, long long>
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define endl '\n'
#define ld long double
#define sz(x) static_cast<int>((x).size())
#define i5 tuple<int,int,int,int,int>
#define all(x) x.begin(), x.end()
#define iiii tuple<int, int,int,int>
#define ld long double
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
struct Node {
int v,s,e,m;
Node *l, *r;
Node (int S,int E){
s=S, e=E, m=(s+e)/2, v=0;
l=r=nullptr;
}
} * roots[200005];
Node* dupe(Node *node){
Node* ret=new Node(node->s,node->e);
ret->v=node->v;
ret->l=node->l; ret->r=node->r;
return ret;
}
void update(Node * node, int S){ // pass pointer *
int & s=node->s, & m=node->m, &e=node->e, &v=node->v;
Node* &l=node->l;
Node* &r= node->r;
if(s==e){
v+=1;
return;
}
if(S<=m){
if(!l) l=new Node(s,m);
else l=dupe(l);
update(l, S);
}
else{
if(!r) r=new Node(m+1,e);
else r=dupe(r);
update(r,S);
}
v=(l?l->v:0)+(r?r->v:0);
//printf("SEGMENT %lld to %lld, v %lld, l %lld, r %lld\n",s,e,v, (l?l->v:0), (r?r->v:0));
}
int bs(int s, int e, int vr, Node * n1, Node * n2){// n1 - n2;
if(!n1) {
//printf("n1 doesnt exist %lld to %lld\n", s, e);
if(vr < s)return -1;
else return vr;
}
assert(s == n1->s and e == n1->e);
int m=(s+e)/2;
// if entire range doesnt work just return -1 immediately.
int sum=n1->v - (n2?n2->v:0);
//printf("value range %lld to %lld, sum %lld\n", s, e, sum);
if(sum + vr < s) {
//printf("range cannot satisfy %lld to %lld, sum %lld\n", s, e, sum);
return -1;
}
if(s==e)return s;
int right=-1;
if(n1->r){
right = bs(m+1, e, vr, n1->r, (n2?n2->r:nullptr));
}
if(right != -1) return right;
int sumonright=(n1->r ? n1->r->v : 0) - (n2?(n2->r? n2->r->v : 0):0);
return bs(s, m, sumonright + vr, n1->l, (n2?n2->l:nullptr));
}
int ans[200005];
const int maxp=200005;
signed main() {
int n, q;cin>>n>>q;
vector<int> ans(q), v(n+1);
vector<pll> qs(q);
for(int i=1;i<=n;i++)cin>>v[i];
for(int i=0;i<q;i++)cin>>qs[i].f>>qs[i].s;
roots[0] = new Node(1, maxp);
for(int i=1;i<=n;i++){
//printf("\nupdating i %lld\n", i);
roots[i]=dupe(roots[i-1]);
update(roots[i], v[i]);
}
for(int i=0;i<q;i++){
auto [l, r] = qs[i];
//printf("\n answering %lld to %lld \n", l, r);
// binary search the difference of roots[r] and roots[l-1]
ans[i]=bs(1, maxp, 0, roots[r], roots[l-1]);
}
for(int i=0;i<q;i++){
cout<<ans[i]<<"\n";
}
return 0;
}
