type
  node=record
    maxl,maxr,maxm,l,r:longint;
    same:boolean;
  end;
var
  tree:array [0..400000] of node;
  a:array [0..100001] of longint;
  n,m:longint;
procedure init;
var
  i:longint;
begin
  read(n); if n=0 then halt; readln(m);
  for i:=1 to n do read(a[i]); readln;
end;
function max(x,y:longint):longint;
begin
  if x>y then exit(x) else exit(y);
end;
procedure updata(var t:node; lt,rt:node);
begin
  t.same:=lt.same and rt.same;
  if lt.l<>rt.l then t.same:=false;
  if lt.same and (lt.r=rt.l) then t.maxl:=lt.maxl+rt.maxl else t.maxl:=lt.maxl;
  if rt.same and (rt.l=lt.r) then t.maxr:=rt.maxr+lt.maxr else t.maxr:=rt.maxr;
  t.maxm:=max(lt.maxm,rt.maxm); if lt.r=rt.l then t.maxm:=max(t.maxm,lt.maxr+rt.maxl);
  t.l:=lt.l; t.r:=rt.r;
end;
procedure buildtree(p,x,y:longint);
begin
  if x=y then
  begin
    tree[p].maxl:=1;
    tree[p].maxr:=1;
    tree[p].maxm:=1;
    tree[p].l:=a[x];
    tree[p].r:=a[x];
    tree[p].same:=true;
    exit;
  end;
  buildtree(p*2,x,(x+y) div 2);
  buildtree(p*2+1,(x+y) div 2+1,y);
  updata(tree[p],tree[p*2],tree[p*2+1]);
end;
function ask(p,x,y,xx,yy:longint):node;
var
  mid:longint; t,lt,rt:node;
begin
  if (x=xx) and (y=yy) then exit(tree[p]);
  mid:=(x+y) div 2;
  if yy<=mid then exit(ask(p*2,x,mid,xx,yy))
  else if xx>mid then exit(ask(p*2+1,mid+1,y,xx,yy))
  else
  begin
    lt:=ask(p*2,x,mid,xx,mid);
    rt:=ask(p*2+1,mid+1,y,mid+1,yy);
    updata(t,lt,rt); exit(t);
  end;
end;
procedure main;
var
  i,x,y:longint; t:node;
begin
  for i:=1 to m do
  begin
    readln(x,y);
    t:=ask(1,1,n,x,y);
    writeln(t.maxm);
  end;
end;
begin
  while true do
  begin
    init;
    buildtree(1,1,n);
    main;
  end;
end.

• 牛 (1920) yygy 2013-10-21 10:11:52