#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int n,q,a[100009],s[100009];
int dp[100009][20];
int log2(int x)
{
	return int(1.0*log(x)/log(2));
}
void rmq_init(int* arr,int N)
{
    for(int i=1;i<=N;i++)
        dp[i][0]=arr[i];
    for(int j=1;(1<<j)<=N;j++)
        for(int i=1;i+(1<<j)-1<=N;i++)
            dp[i][j]=max(dp[i][j-1],dp[i+(1<<j-1)][j-1]);
}
int rmq(int l,int r)
{
    int k=log2(r-l+1);
    return max(dp[l][k],dp[r-(1<<k)+1][k]);
}
int main()
{
	ios::sync_with_stdio(0);
	while(cin>>n>>q&&n)
	{
		memset(s,0,sizeof(s));
		int cur=1;
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<n;i++)
		{
			while(a[i]==a[i+1]&&i<n)s[cur]++,i++;
			cur++;
		}
		cur--;
		rmq_init(s,cur);
		while(q--)
		{
			int l,r;cin>>l>>r;
			int L=upper_bound(s+1,s+cur+1)-s-1,R=lower_bound(s+1,s+cur+1)-s-1;
			cout<<max(max(s[L]-l,r-s[R]),rmq(L,R));
		}
	}
  	return 0;
}