#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
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=710;
int Maxn;
struct node{
	int l,r;
	int Max,tag;
}tr[M][M<<2];
int tt[N];
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 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;
	}
}
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);
	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);
	return Ans(u<<1|1,x,id);
}
int len;
struct QQ{
	int l,r,id;
	friend il 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)
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() { 
	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=max(1,sqrt(Max)-10);
	Maxn=bl(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);
	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() {
	while(T--) {
		solve();
	}
	return false;
}
/*
3 1
1 2 2
1 3
*/

answer.code: In function ‘void solve()’:
answer.code:119:15: error: no matching function for call to ‘max(int, __gnu_cxx::__enable_if<true, double>::__type)’
  119 |         ll=max(1,sqrt(Max)-10);
      |            ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from answer.code:1:
/usr/include/c++/13/bits/stl_algobase.h:257:5: note: candidate: ‘template<class _Tp> const _Tp& std::max(const _Tp&, const _Tp&)’
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
answer.code:119:15: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’})
  119 |         ll=max(1,sqrt(Max)-10);
      |            ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note: candidate: ‘template<class _Tp, class _Compare> const _Tp& std::max(const _Tp&, const _Tp&, _Compare)’
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algobase.h:303:5: note:   template argument deduction/substitution failed:
answer.code:119:15: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘__gnu_cxx::__enable_if<true, double>::__type’ {aka ‘double’})
  119 |         ll=max(1,sqrt(Max)-10);
      |            ~~~^~~~~~~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61:
/usr/include/c++/13/bits/stl_algo.h:5795:5: note: candidate: ‘template<class _Tp> _Tp std::max(initializer_list<_Tp>)’
 5795 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5795:5: note:   template argument deduction/substitution failed:
answer.code:119:15: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  119 |         ll=max(1,sqrt(Max)-10);
      |            ~~~^~~~~~~~~~~~~~~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note: candidate: ‘template<class _Tp, class _Compare> _Tp std::max(initializer_list<_Tp>, _Compare)’
 5805 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/13/bits/stl_algo.h:5805:5: note:   template argument deduction/substitution failed:
answer.code:119:15: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
  119 |         ll=max(1,sqrt(Max)-10);
      |            ~~~^~~~~~~~~~~~~~~~