/* Peter Schaeffer */
#include <stdio.h>

#define SIZE 256
#define MIN(a,b) ({int _a=(a), _b=(b); (_a<_b)?(_a):(_b);})
#define MAX(a,b) ({int _a=(a), _b=(b); (_a>_b)?(_a):(_b);})

FILE *in;

int n, q, nx[100000+SIZE], l[(100000+SIZE)/SIZE], r[(100000+SIZE)/SIZE], c[(100000+SIZE)/SIZE], v[(100000+SIZE)/SIZE], gres;

int search(int l, int r)
{
  int res=nx[l], start=l;
  gres=1;
  for(int i=l+1; i<=r; i++)
    {
      if (nx[start]==nx[i])
	{
	  if (i-start+1>gres)
	    {
	      gres=i-start+1;
	      res=nx[i];
	    }
	}
      else
	{
	  start=i;
	}
    }
  return res;
}

int main()
{
  in=stdin;
  while(1)
    {
      fscanf(in, " %d %d ", &n, &q);
      if (!n) break;
      for(int i=0; i<n; i++)
	fscanf(in, " %d ", &nx[i]);
      for(int i=n; i<100000+SIZE; i++) nx[i]=i+100000;      
      for(int i=0; i<(n+SIZE-1)/SIZE; i++)
	{
	  r[i]=l[i]=0;
	  while((l[i]<SIZE) && (nx[l[i]+i*SIZE]==nx[i*SIZE])) l[i]++;
	  while((r[i]<SIZE) && (nx[SIZE-1-r[i]+i*SIZE]==nx[SIZE-1+i*SIZE])) r[i]++;
	  v[i]=search(i*SIZE, i*SIZE+SIZE-1);
	  c[i]=gres;
	  // printf("%d %d/%d %d\n", l[i], v[i], c[i], r[i]);
	}

      for(int qx=0; qx<q; qx++)
	{
	  int x, y;
	  fscanf(in, " %d %d ", &x, &y);
	  x--; y--;
	  int resc=0, resv=0, count=0, val=0;
	  resv=search(x, MIN(y, x|(SIZE-1)));
	  resc=gres;
	  val=nx[x|(SIZE-1)];
	  for(int i=MIN(y, x|(SIZE-1)); i>=x; i--)
	    if (nx[i]==val) count++;
	  for(int i=x/SIZE+1; i<y/SIZE; i++)
	    {
	      if ((count+l[i]>resc) && (val==nx[i*SIZE]))
		{
		  resc=count+l[i];
		  resv=val;
		}
	      if ((c[i]>resc))
		{
		  resc=c[i];
		  resv=v[i];
		}
	      if (val==nx[i*SIZE+SIZE-1])
		count=r[i]+count;
	      else
		count=r[i];
	      val=nx[i*SIZE+SIZE-1];
	    }
	  for(int i=MAX((x|(SIZE-1))+1, y&(~(SIZE-1))); i<=y; i++)
	    if (nx[i]==val) count++;
	  if (count>resc)
	    {
	      resc=count; resv=val;
	    }
	  if (MAX((x|(SIZE-1))+1, y&(~(SIZE-1)))<=y)
	    {
	      val=search(MAX((x|SIZE-1)+1, y&(~(SIZE-1))), y);
	      if (gres>resc)
		{
		  resc=gres; resv=val;
		}
	    }
	  printf("%d\n", resc);
	}
    }
  return 0;
}
