var
    i,j,q,x,z,y,n,m,k,ll:longint;
    ma:array[1..100000,0..18]of longint;
    l,r,a,b:array[0..100000]of longint;

  function max(x,y:longint):longint;
    begin
      if x>y then exit(x);
      exit(y);
    end;

  function min(x,y:longint):longint;
    begin
      if x<y then exit(x);
      exit(y);
    end;

  function rmq(x,y:longint):longint;
    var
      i,kk,zz:longint;
    begin
      if x>y then exit(0);
      rmq:=0;
      kk:=y-x+1;
      zz:=trunc(ln(kk)/ln(2));
      rmq:=max(ma[x,zz],ma[y-1<<zz+1,zz]);
    end;

  begin
    while not eof do
      begin
        fillchar(ma,sizeof(ma),0);
        fillchar(b,sizeof(b),0);
        fillchar(a,sizeof(a),0);

        readln(n,q);
        if n=0 then break;
        for i:=1 to n do read(a[i]);
        readln;
        b[1]:=1;
        for i:=2 to n do
          if a[i]=a[i-1] then b[i]:=b[i-1]
            else b[i]:=b[i-1]+1;

        for i:=1 to n do inc(ma[b[i],0]);
        ll:=b[n];
        for j:=1 to trunc(ln(ll)/ln(2)) do
          for i:=1 to ll-1<<j+1 do
            ma[i,j]:=max(ma[i,j-1],ma[i+1<<(j-1),j-1]);

        l[1]:=0;
        for i:=2 to n do
          if a[i]=a[i-1] then l[i]:=l[i-1]
            else l[i]:=i-1;
        r[n]:=n+1;
        for i:=n-1 downto 1 do
          if a[i]=a[i+1] then r[i]:=r[i+1]
            else r[i]:=i+1;

        for i:=1 to q do
          begin
            readln(x,y);
            z:=0;
            z:=max(z,min(r[x],y+1)-x);
            z:=max(z,y-max(x-1,l[y]));
            z:=max(z,rmq(b[r[x]],b[l[y]]));
            writeln(z);
          end;
      end;
  end.