#include<stdio.h>
#include<string.h>
#define lson l , m , rt<<1
#define rson m + 1 , r , rt<<1|1

const int maxn = 100005 ;
int lmax[maxn<<2] , rmax[maxn<<2] , mmax[maxn<<2] , lp[maxn<<2] , rp[maxn<<2] ;
int max ( int a , int b ) { return a > b ? a : b ; }

void push_up ( int rt , int m )
{
	mmax[rt] = max ( mmax[rt<<1] , mmax[rt<<1|1] ) ;
	lmax[rt] = lmax[rt<<1] , rmax[rt] = rmax[rt<<1|1] ;
	lp[rt] = lp[rt<<1] , rp[rt] = rp[rt<<1|1] ;
	if ( rp[rt<<1] == lp[rt<<1|1] ) mmax[rt] = max ( mmax[rt] , rmax[rt<<1] + lmax[rt<<1|1] ) ;
	if ( lmax[rt<<1] == m - (m>>1) && rp[rt<<1] == lp[rt<<1|1] ) lmax[rt] += lmax[rt<<1|1] ;
	if ( rmax[rt<<1|1] == m>>1 && rp[rt<<1] == lp[rt<<1|1] ) rmax[rt] += rmax[rt<<1] ;
}

void build ( int l , int r , int rt )
{
	if ( l == r )
	{
		int a ;
		scanf ( "%d" , &a ) ;
		mmax[rt] = lmax[rt] = rmax[rt] = 1 ;
		lp[rt] = rp[rt] = a ;
		return ;
	}
	int m = ( l + r ) >> 1 ;
	build ( lson ) ;
	build ( rson ) ;
	push_up ( rt , r - l + 1 ) ;
}

int query ( int a , int b , int l , int r , int rt )
{
	if ( a <= l && r <= b ) { return mmax[rt] ; }
	int ret = 0 ;
	int m = ( l + r ) >> 1 ;
	if ( a <= m ) ret = max ( ret , query ( a , b , lson ) ) ;
	if ( m < b ) ret = max ( ret , query ( a , b , rson ) ) ;
	if ( rp[rt<<1] == lp[rt<<1|1] && a <= m && m < b )
	{
		int x = rmax[rt<<1] ; int y = lmax[rt<<1|1] ;
		if ( m - x + 1 <= a - 1 ) x = m - a + 1 ;
		if ( m + y >= b + 1 ) y = b - m ;
		ret = max ( ret , x + y ) ;
	}
	return ret ;
}

int main ()
{
	int n , q ;
	while ( scanf ( "%d" , &n ) != EOF )
	{
		if ( n == 0 ) break ;
		scanf ( "%d" , &q ) ;
		build ( 1 , n , 1 ) ;
		while ( q -- )
		{
			int x , y ;
			scanf ( "%d%d" , &x , &y ) ;
			if ( x == y )
			{
				puts ( "1" ) ;
				continue ;
			}
			printf ( "%d\n" , query ( x , y , 1 ,n , 1 ) ) ;
		}
	}
	return 0 ;
}