#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 fire signed
#define il inline
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;
int Maxn;
struct node{
	int l,r;
	int Max,tag;
}tr[M][M<<2];
int tt[M];
//#define max(x,y) ((x)<(y)?(y):(x))
il void up(int x,int id) {
	tr[id][x].Max=max(tr[id][x<<1].Max,tr[id][x<<1|1].Max);
}
int lowbit(int x) {
	return x&-x;
}
void add(int x,int k) {
	for(;x<=Maxn;x+=lowbit(x)) tt[x]+=k;
}
int Ans(int x) {
	int res=0;
	for(;x;x-=lowbit(x)) res+=tt[x];
	return res;
}
il 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);
}
il 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);
	tr[id][u].Max=max(tr[id][u<<1].Max,tr[id][u<<1|1].Max)+tr[id][u].tag;
//	up(u,id);
}
il 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)+tr[id][u].tag;
	return Ans(u<<1|1,x,id)+tr[id][u].tag;
}
int len;
struct QQ{
	int l,r,id,L;
	friend il bool operator<(const QQ&a,const QQ&b) {
		return a.L!=b.L?a.l<b.l:(((a.L)&1)?a.r<b.r: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)
il void add(int x) {
	int itl=bl(x);
	int bln=bl(Max);
	modify(1,x,R(itl),1,itl);
	itl++;
	if(itl<=bln) add(itl,1);
}
il void del(int x) {
	int itl=bl(x);
	int bln=bl(Max);
	modify(1,x,R(itl),-1,itl);
	itl++;
	if(itl<=bln) add(itl,-1);
}
void solve() { 
	unsigned int x=1281298;
	rep(i,1,5000000000) {
		x^=x<<13,x^=x>>7,x^=x<<19;
	}
	assert(x);
	return;
	in(n),in(q);
	rep(i,1,n) in(a[i]),a[i]++,Max=max(Max,a[i]);
	Max=max(Max,n);
	len=sqrt(n);
	ll=sqrt(Max);
	Maxn=bl(Max);
	rep(i,1,q) {
		in(s[i].l),in(s[i].r);
		s[i].L=s[i].l/len; 
		s[i].id=i;
	}
	stable_sort(s+1,s+1+q);
	rep(i,1,bl(Max)) build(1,L(i),R(i),i);
	int L=0,R=0;
	L=1,R=n;
	rep(i,1,n) add(a[i]);
	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--]);
		int lst=false,ss=0;
		rep1(j,bl(Max),1) {
			int id=tr[j][1].Max,pl=Ans(j);
			id+=pl;
			if(id>=0) {
				lst=j;
				ss=pl;
				break;
			}
		}
		int res=0;
		rep1(j,R(lst),L(lst)) {
			if(ss+Ans(1,j,lst)>=0) {
				res=j;
				break;
			}
		}
		ans[s[i].id]=res;
	}
	rep(i,1,q) printf("%d\n",ans[i]);
}
fire main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	while(T--) {
		solve();
	}
	return false;
}
/*
3 1
1 2 2
1 3
*/