#include <bits/stdc++.h>
using namespace std;

template <class T> int sz(T&& a) { return int(size(forward<T>(a))); }

template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;

using ll = int64_t;
using vi = vc<int>;

template <class F>
struct ycr {
	F f;
	
	template <class T>
	explicit ycr(T&& f_) : f(forward<T>(f_)) {}

	template <class... Args>
	decltype(auto) operator()(Args&&... args) {
		return f(ref(*this), forward<Args>(args)...);
	}
};
template <class F>
decltype(auto) yc(F&& f) {
	return ycr<decay_t<F>>(forward<F>(f));
}

const int N=1e5+5;
int n,m;
int a[N],b[N],re[N],len=0;
inline int ask(int x)
{
	return lower_bound(re+1,re+len+1,x)-re;
}
int st[N][20], lg[N];
inline int ask_max(int lef,int rig)
{
	int k=lg[rig-lef+1];
	return max(st[lef][k],st[rig-(1<<k)+1][k]);
}

struct node{
	int l,r,id;
}qry[N];
inline bool cmp1(node x,node y)
{
	return x.r<y.r;
}
inline bool cmp2(node x,node y)
{
	return x.l>y.l;
}

int maxx[N*4];
inline void update(int k)
{
	maxx[k]=max(maxx[k*2],maxx[k*2+1]);
}
inline void update_val(int lef,int rig,int k,int place,int c)
{
	if(lef==rig) 
	{
		maxx[k]=max(maxx[k],c);
		return;
	}
	int mid=(lef+rig)>>1;
	if(place<=mid) update_val(lef,mid,k*2,place,c);
	else update_val(mid+1,rig,k*2+1,place,c);
	update(k);
}
inline int Ask(int lef,int rig,int k,int l,int r)
{
	if(l<=lef && r>=rig)
	{
		return maxx[k];
	}
	int ans=0;
	int mid=(lef+rig)>>1;
	if(l<=mid) ans=max(ans,Ask(lef,mid,k*2,l,r));
	if(r>mid) ans=max(ans,Ask(mid+1,rig,k*2+1,l,r));
	return ans;
}

int lef[N], rig[N], pos[N];
int ans[N];
int main() {
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	cout << fixed << setprecision(20);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i], b[i]=a[i];
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
		if(b[i]!=b[i-1])
			re[++len]=b[i];
	for(int i=1;i<=n;i++) a[i]=ask(a[i]);
	for(int i=1;i<=n;i++) st[i][0]=a[i], lg[i]=log2(i);
	for(int j=1;j<=lg[n];j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	for(int i=1;i<=n;i++) pos[i]=0;
	for(int i=1;i<=n;i++)
	{
		lef[i]=pos[a[i]];
		if(!lef[i]) lef[i]=i;
		pos[a[i]]=i;
	}
	for(int i=1;i<=n;i++) pos[i]=n+1;
	for(int i=n;i>=1;i--)
	{
		rig[i]=pos[a[i]];
		if(rig[i]==n+1) rig[i]=i;
		pos[a[i]]=i;
	}
	for(int i=1;i<=n;i++)
	{
		if(ask_max(lef[i],i)<=a[i]) lef[i]=lef[lef[i]];
		else lef[i]=i;
	}
	//for(int i=1;i<=n;i++) cout<<lef[i]<<" ";
	//cout<<endl;
	for(int i=n;i>=1;i--)
	{
		if(ask_max(i,rig[i])<=a[i]) rig[i]=rig[rig[i]];
		else rig[i]=i;
	}
	for(int i=1;i<=m;i++) cin>>qry[i].l>>qry[i].r, qry[i].id=i;
	sort(qry+1,qry+m+1,cmp1);
	memset(maxx,0,sizeof(maxx));
	int p=1;
	for(int i=1;i<=m;i++)
	{
		while(p<=qry[i].r)
		{
			if(lef[p]!=0) update_val(1,n,1,lef[p],p-lef[p]);
			p++;
		}
		ans[qry[i].id]=max(ans[qry[i].id],Ask(1,n,1,qry[i].l,qry[i].r));
	}
	sort(qry+1,qry+m+1,cmp2);
	memset(maxx,0,sizeof(maxx));
	p=n;
	for(int i=1;i<=m;i++)
	{
		while(p>=qry[i].l)
		{
			if(rig[p]!=n+1) update_val(1,n,1,rig[p],rig[p]-p);
			p--;
		}
		ans[qry[i].id]=max(ans[qry[i].id],Ask(1,n,1,qry[i].l,qry[i].r));
	}
	for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
}