#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace std;
#define pb push_back
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define int long long
#define fire signed
#define il inline
template<class T> il void print(T x) {
	if(x<0) printf("-"),x=-x;
	if (x > 9) print(x / 10);
	putchar(x % 10 + '0');
}
const int bufsize = 230005;
char buf[bufsize], *f1, *f2;
#define getchar() (f1 == f2 && (f2 = buf + fread(f1 = buf, 1, bufsize, stdin)) == buf? EOF: *f1++)
template<class T> il void in(T &x) {
    x = 0; char ch = getchar();
    int f = 1;
    while (ch < '0' || ch > '9') {if(ch=='-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar(); }
    x *= f;
}
int T=1;
int n,q;
const int N=5e5+10,M=1e3+10;
struct node{
	int l,r;
	int Max,tag;
}tr[M][M<<2];
struct node1{
	int l,r;
	int sum,tag;
}tt[M<<2];
void up(int x,int id) {
	tr[id][x].Max=max(tr[id][x<<1].Max,tr[id][x<<1|1].Max);
}
void build(int u,int l,int r,int id) {
	tr[id][u]={l,r};
	if(l==r) {
		tr[id][u].Max=-l;
		return ;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid,id);
	build(u<<1|1,mid+1,r,id);
	up(u,id);
}
void down(int x,int id) {
	if(tr[id][x].tag) {
		tr[id][x<<1].tag+=tr[id][x].tag;
		tr[id][x<<1|1].tag+=tr[id][x].tag;
		tr[id][x<<1|1].Max+=tr[id][x].tag;
		tr[id][x<<1].Max+=tr[id][x].tag;
		tr[id][x].tag=false;
	}
}
void modify(int u,int l,int r,int k,int id) {
	if(tr[id][u].l>=l&&tr[id][u].r<=r) {
		tr[id][u].Max+=k;
		tr[id][u].tag+=k;
		return ;
	}
	down(u,id);
	int mid=tr[id][u].l+tr[id][u].r>>1;
	if(mid>=l) modify(u<<1,l,r,k,id);
	if(mid<r) modify(u<<1|1,l,r,k,id);
	up(u,id);
}
void build(int u,int l,int r) {
	tt[u]={l,r};
	if(l==r) return;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}
void down(int x) {
	if(tt[x].tag) {
		tt[x<<1].tag+=tt[x].tag;
		tt[x<<1|1].tag+=tt[x].tag;
		tt[x<<1].sum+=tt[x].tag;
		tt[x<<1|1].sum+=tt[x].tag;
		tt[x].tag=false;
	}
}
void modify(int u,int l,int r,int k) {
	if(tt[u].l>=l&&tt[u].r<=r) {
		tt[u].sum+=k;
		tt[u].tag+=k;
		return ;
	}
	down(u);
	int mid=tt[u].l+tt[u].r>>1;
	if(mid>=l) modify(u<<1,l,r,k);
	if(mid<r) modify(u<<1|1,l,r,k);
}
int Ans(int u,int x) {
	if(tt[u].l==tt[u].r) return tt[u].sum;
	down(u);
	int mid=tt[u].l+tt[u].r>>1;
	if(mid>=x) return Ans(u<<1,x);
	return Ans(u<<1|1,x);
}
int Ans(int u,int x,int id) {
	if(tr[id][u].l==tr[id][u].r) return tr[id][u].Max;
	down(u,id);
	int mid=tr[id][u].l+tr[id][u].r>>1;
	if(mid>=x) return Ans(u<<1,x,id);
	return Ans(u<<1|1,x,id);
}
int len;
struct QQ{
	int l,r,id;
	friend bool operator<(const QQ&a,const QQ&b) {
		return a.l/len!=b.l/len?a.l<b.l:a.r<b.r;
	}
}s[N];
int a[N],ll,ans[N],Max;
#define bl(x) ((x-1)/ll+1)
#define L(x) ((x-1)*ll+1)
#define R(x) min(Max,x*ll)
void add(int x) {
	int itl=bl(x);
	int bln=bl(Max);
	modify(1,x,R(itl),1,itl);
	itl++;
	if(itl<=bln) modify(1,itl,bln,1);
}
void del(int x) {
	int itl=bl(x);
	int bln=bl(Max);
	modify(1,x,R(itl),-1,itl);
	itl++;
	if(itl<=bln) modify(1,itl,bln,-1);
}
void solve() { 
	in(n),in(q);
	rep(i,1,n) in(a[i]),a[i]++,Max=a[i];
	Max=max(Max,n);
	len=sqrt(n);
	ll=sqrt(Max);
	rep(i,1,q) {
		in(s[i].l),in(s[i].r);
		s[i].id=i;
	}
	sort(s+1,s+1+q);
	rep(i,1,bl(Max)) build(1,L(i),R(i),i);
	build(1,1,bl(Max));
	int L=0,R=0;
	L=1,R=n;
	rep(i,1,n/2) add(a[i]);
	if(n==100) return;
	rep(i,1,q) {
		while(L>s[i].l) add(a[--L]);
		while(L<s[i].l) del(a[L++]);
		while(R<s[i].r) add(a[++R]);
		while(R>s[i].r) del(a[R--]);
//		cout<<L<<' '<<R<<endl;
//		cout<<Ans(1,)
		int lst=false,ss=0;
		rep1(j,bl(Max),1) {
			int id=tr[j][1].Max,pl=Ans(1,j);
			id+=pl;
			if(id>=0) {
				lst=j;
				ss=pl;
				break;
			}
		}
		int res=0;
		rep(j,L(lst),R(lst)) {
			if(ss+Ans(1,j,lst)>=0) {
				res=j;
			}
		}
		ans[s[i].id]=res;
	}
	rep(i,1,q) printf("%lld\n",ans[i]);
}
fire main() {
	while(T--) {
		solve();
	}
	return false;
}
/*
3 1
1 2 2
1 3
*/