#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<math.h>
using namespace std;
typedef long long ll;
//typedef __int64 int64;
const int maxn = 201005;
const int maxm = 100000;
const int inf = 99999999;
const double pi=acos(-1.0);
const double eps = 1e-8;

int a[ maxn ];
map<int,int>mp;
int cnt[ maxn ];
int bit[ 32 ];
int dp[ maxn ][ 32 ];
void init(){
	mp.clear();
	memset( dp,0,sizeof( dp ) );
	memset( cnt,0,sizeof( cnt ));
}
void init_bit( ){
	bit[ 0 ] = 1;
	bit[ 1 ] = 2;
	for( int i=2;i<32;i++ ){
		bit[ i ] = 2*bit[ i-1 ];
		//printf("bit[%d]=%d\n",i,bit[i]);
	}
}

int fmax( int x,int y ){
	if( cnt[ x ]>cnt[ y ] )
		return x;
	else return y;
}

void ST( int n ){
	int k = (int)( log(1.0*n)/log(2.0) );
	for( int i=0;i<=n;i++ )
		dp[ i ][ 0 ] = i;
	for( int j=1;j<=k;j++ ){
		for( int i=1;i<=n-bit[j]+1;i++ ){
			dp[ i ][ j ] = fmax( dp[ i ][ j-1 ],dp[ i+bit[ j-1 ] ][ j-1 ] );
		}
	}
}
int RMQ( int l,int r ){
	if( l>r ) swap( l,r );
	int k = (int)(log( (r-l+1)*1.0 )/log( 2.0 ));
	//printf("k = %d\n",k);
	//printf("s1=%d s2=%d\n",l,r-bit[k]+1);
	return fmax( dp[ l ][ k ],dp[ r-bit[k]+1 ][ k ] );
}

int main(){
	//freopen( "in.txt","r",stdin );
	//freopen( "out.txt","w",stdout );
	init_bit();
	int n,q;
	while( scanf("%d",&n)!=EOF ){
		if( n==0 ) {
			//printf("\n");
			break;
		}
		scanf("%d",&q);
		init();
		cnt[ 0 ] = 0;
		a[ 0 ] = inf;
		a[ n+1 ] = inf;
		for( int i=1;i<=n;i++ ){
			scanf("%d",&a[ i ]);
			mp[ a[i] ]++;
			cnt[ i ] = mp[ a[i] ];
		}
		ST( n+1 );
		int aa,bb;
		
		while( q-- ){
			scanf("%d%d",&aa,&bb);
			int l = aa;
			int r = bb;
			if( a[ aa ]==a[ bb ] ){
				printf("%d\n",bb-aa+1 );
				continue;
			}//
			int flag = -1;
			if( a[ aa ]==a[ aa-1 ] ){
				while( a[ l ]==a[ aa ] ){
					flag = l;
					l++;
				}
			}
			int ans = cnt[ RMQ( l,r ) ];
			ans = max( ans,cnt[ flag ]-cnt[ aa-1 ] );
			printf("%d\n",ans);
		}
	}
	return 0;
}