记录编号	50727	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十二]奶牛排队	最终得分	100
用户昵称	DavidMason	是否通过	通过
代码语言	Pascal	运行时间	0.573 s
提交时间	2012-11-29 17:19:40	内存使用	9.70 MiB

type rr=record
     l,r,max,min,maxpos,minpos:longint;
end;

var
  tree:array[0..400000] of rr;
  a:array[0..100000] of longint;
  min,max,minl,maxr,left,right,maxpos,minpos,n,maxrmq:longint;

procedure init;
begin
  assign(input,'tahort.in'); reset(input);
  assign(output,'tahort.out'); rewrite(output);
end;

procedure terminate;
begin
  close(input); close(output);halt;
end;

procedure build(t,l,r:longint);
var
  mid:longint;
begin
  tree[t].l:=l; tree[t].r:=r;
  tree[t].max:=-maxlongint; tree[t].min:=maxlongint;
  tree[t].maxpos:=-maxlongint; tree[t].minpos:=maxlongint;
  if l=r then exit;
  mid:=(l+r) div 2;
  build(t*2,l,mid); build(t*2+1,mid+1,r);
end;

procedure insert(t,i,value:longint);
var
  mid:longint;
begin
  if (tree[t].l=i) and (tree[t].r=i) then begin
      tree[t].max:=value; tree[t].min:=value;
      tree[t].maxpos:=i; tree[t].minpos:=i;
      exit;
  end;
  if value>tree[t].max then begin
     tree[t].max:=value;
     tree[t].maxpos:=i;
  end else if value=tree[t].max then begin
     if tree[t].maxpos<i then tree[t].maxpos:=i;
  end;
  if value<tree[t].min then begin
     tree[t].min:=value;
     tree[t].minpos:=i;
  end else if value=tree[t].min then begin
     if tree[t].minpos>i then tree[t].minpos:=i;
  end;
  mid:=(tree[t].l+tree[t].r) div 2;
  if i<=mid then insert(t*2,i,value) else insert(t*2+1,i,value);
end;

procedure get(t,l,r:longint);
var
  mid:longint;
begin
  if (tree[t].l=l) and (tree[t].r=r) then begin
      if tree[t].max>max then begin
         max:=tree[t].max;
         maxpos:=tree[t].maxpos;
      end else if tree[t].max=max then begin
         if tree[t].maxpos>maxpos then maxpos:=tree[t].maxpos;
      end;
      if tree[t].min<min then begin
         min:=tree[t].min;
         minpos:=tree[t].minpos;
      end else if tree[t].min=min then begin
         if tree[t].minpos<minpos then minpos:=tree[t].minpos;
      end;
      exit;
  end;
  mid:=(tree[t].l+tree[t].r) div 2;
  if r<=mid then get(t*2,l,r) else
  if l>=mid+1 then get(t*2+1,l,r) else begin
     get(t*2,l,mid);
     get(t*2+1,mid+1,r);
  end;
end;

procedure dfs(l,r:longint);
var
  maxx,minn,t:longint;
begin
  if l>r then exit;
  max:=-maxlongint; min:=maxlongint;
  maxpos:=-maxlongint; minpos:=maxlongint;
  if l=r then begin
     max:=a[l]; min:=a[l];
     maxpos:=l; minpos:=l;
  end else get(1,l,r);
  if maxpos>minpos then begin
     if maxpos-minpos>maxrmq then begin
        maxrmq:=maxpos-minpos;
        left:=minpos; right:=maxpos;
        maxr:=max; minl:=min;
     end;
  end else begin
      t:=maxpos; maxpos:=minpos; minpos:=t;
  end;
  maxx:=maxpos; minn:=minpos;
  if l=r then exit;
  dfs(l,minn);
  dfs(minn+1,maxx-1);
  dfs(maxx,r);
end;

procedure main;
var
  i,ans:longint;
begin
  read(n); build(1,1,n); maxrmq:=-maxlongint;
  for i:=1 to n do begin
      read(a[i]);
      insert(1,i,a[i]);
  end;
  dfs(1,n); ans:=0;
  if left<>right then writeln(right-left+1) else writeln(0);
end;

begin
  init;
  main;
  terminate;
end.