#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=1e6;
unordered_map<int,int>mp;
int a[N],b[N],c[N];
int n,m,f[N][26],lg2[N];
int query(int l,int r)
{
    int k=lg2[r-l+1];
    return max(f[l][k],f[r-(1<<k)+1][k]);
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,r=0;i<=n;i++)
    {
        while(r+1<=n && !mp[a[r+1]] ) mp[a[++r]]=1;               
        b[i]=r-i+1;
        mp[a[i]]=0;
    }
    mp.clear();
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
    {
        if(mp[a[i]])c[i]=min(c[i-1]+1,i-mp[a[i]]);//若a[i]出现过，则分两种情况 
        else        c[i]=c[i-1]+1;                //若a[i]没出现过
        mp[a[i]]=i;
    }
	lg2[1]=0;for(int i=2;i<=n;i++)lg2[i]=lg2[i>>1]+1;
	//f[i][j]表示位置i至位置i+2^j-1中最大的b 
	for(int i=1;i<=n;i++)f[i][0]=b[i];
	int D=log2(n); 
	for(int j=1;j<=D;j++)
		for(int i=1;i+(1<<j)-1<=n;i++)
			f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	
	for(int i=1,l,r,ans;i<=m;i++)
	{
		scanf("%d%d",&l,&r);l++,r++;
		if(r-c[r]+1<=l)ans=r-l+1;
		else           ans=max(c[r],query(l,r-c[r]));
		printf("%d\n",ans);
	}
	return 0;
}