/* 
 * Problem: pku3368 Frequent values
 * Author: Guo Jiabao
 * Time: 2009.4.1 19:30
 * State: Solved
 * Memo: RQM SparseTable
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
const int MAXN=100001,LG=18,INF=0x7FFFFFFF;
using namespace std;
int M,N,Q;
int A[MAXN],Map[MAXN],F[MAXN][LG],Start[MAXN],Log[MAXN];
void init()
{
	int i,k;
	freopen("frequent.in","r",stdin);
	freopen("frequent.out","w",stdout);
	A[N=0]=INF;
	for (i=1,k=0;i<MAXN;i++)
	{
		if (1<<(k+1)<=i)
			k++;
		Log[i]=k;
	}
}
bool readfile()
{
	scanf("%d",&M);
	if (M==0) return false;
	scanf("%d",&Q);
	for (int i=1;i<=M;i++)
	{
		scanf("%d",&A[i]);
		if (A[i]!=A[i-1])
		{
			Map[i]=++N;
			Start[N]=i;
			F[N][0]=1;
		}
		else
		{
			Map[i]=N;
			F[N][0]++;
		}
	}
	return true;
}
inline int Max(int a,int b){return a>b?a:b;}
void SpraseTable()
{
	int i,j,jt;
	for (j=jt=1;jt<=N;j++,jt=jt<<1)
	{
		for (i=1;i+jt<=N;i++)
		{
			F[i][j]=Max(F[i][j-1],F[i+jt][j-1]);
		}
	}
}
void Query()
{
	int i,ta,tb,a,b,k,tk,Ans;
	for (i=1;i<=Q;i++)
	{
		scanf("%d%d",&ta,&tb);
		a=Map[ta];b=Map[tb];
		if (a==b)
			Ans=tb-ta+1;
		else if (b==a+1)
			Ans=Max(Start[b]-ta,tb-Start[b]+1);
		else
		{
			Ans=Max(Start[a+1]-ta,tb-Start[b]+1);
			a++;b--;
			k=Log[b-a+1];
			tk=1<<k;
			Ans=Max(Ans,F[a][k]);
			Ans=Max(Ans,F[b-tk+1][k]);
		}
		printf("%dn",Ans);
	}
}
int main()
{
	init();
	while (readfile())
	{
		SpraseTable();
		Query();
	}
}