import java.util.*;
class Node
{
	int left;
	int right;
	int num;
	int count;
	public Node()
	{
		
	}
	public Node(int left,int right,int num,int count)
	{
		this.left=left;
		this.right=right;
		this.count=count;
		this.num=num;
	}
}
public class Main
{
	static Scanner scan=new Scanner(System.in);
	static final int MAX=100010;
	static int leng,query,kind;
	static int array[]=new int[MAX];
	static int hash[]=new int[MAX];
	static Node point[]=new Node[MAX];
	static Node tree[]=new Node[MAX*4];
	public static void init()
	{
		int i;
		for(i=1;i<=leng;i++)
		{
			array[i]=scan.nextInt();
		}
		point[1]=new Node(1,1,array[1],1);
		hash[1]=1;
		for(kind=1,i=2;i<=leng;i++)
		{
			if(array[i]==array[i-1])
			{
				point[kind].count++;
				point[kind].right=i;
			}
			else
			{
				kind++;
				point[kind]=new Node(i,i,array[i],1);
			}
			hash[i]=kind;
		}
	}
	public static void build(int pos,int left,int right)
	{
		if(left==right)
		{
			tree[pos].count=point[left].count;
			tree[pos].left=left;
			tree[pos].right=right;
			return ;
		}
		int mid=(left+right)>>1;
		build(pos*2,left,mid);
		build(pos*2+1,mid+1,right);
		tree[pos].right=right;
		tree[pos].left=left;
		if(tree[pos*2].count>tree[pos*2+1].count)
		{
			tree[pos].count=tree[pos*2].count;			
		}
		else
		{
			tree[pos].count=tree[pos*2+1].count;
		}
	}
	public static int getsum(int pos,int left,int right)
	{
		if(tree[pos].left>=left&&tree[pos].right<=right&&tree[pos].count!=0)
		{
			return tree[pos].count;
		}
		int mid=(tree[pos].left+tree[pos].right)>>1;
		if(mid>=right)
			return getsum(pos*2,left,right);
		else if(mid<left)
			return getsum(pos*2+1,left,right);
		else
		{
		    int l=getsum(pos*2,left,right);
		    int r=getsum(pos*2+1,left,right);
		    return l>r?l:r;
		}
	}
	public static int slove(int start,int end)
	{
		if(hash[start]==hash[end])
		   return hash[end]-hash[start]+1;
		else if(hash[start]==hash[end]-1)
		{
			int fre1=point[hash[start]].right-start+1;
			int fre2=end-point[hash[end]].left+1;
			return fre1>fre2?fre1:fre2;
		}
		else
		{
			int fre1=point[hash[start]].right-start+1;
			int fre2=end-point[hash[end]].left+1;
			fre1=fre1>fre2?fre1:fre2;	
			int ans=getsum(1,hash[start]+1,hash[end]-1);
		    return ans>fre1?ans:fre1;
		}
	}
	public static void main(String[] args)
	{
       for(int i=1;i<MAX*4;i++)
    	   tree[i]=new Node();
       while(true)
       {
    	  int i,start,end;
          leng=scan.nextInt();
          if(leng==0)
        	  break;
          query=scan.nextInt();
          init();
          build(1,1,kind);
          for(i=1;i<=query;i++)
          {
           start=scan.nextInt();
           end=scan.nextInt();
           System.out.println(slove(start,end));   
          }
       }
	}

}