KAGAIN - Chiến trường Ô qua
Tác giả: RR
Ngôn ngữ: Pascal
var
a,left,right,stack:array[0..30111] of longint;
tmp,i,n,test,top:longint;
lr,lu,lv:longint;
begin
read(test); a[0]:=0;
for test:=1 to test do
begin
read(n);
for i:=1 to n do read(a[i]);
lr:=0;
top:=0; stack[0]:=0;
for i:=1 to n do
begin
while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
left[i]:=stack[top]+1;
inc(top); stack[top]:=i;
end;
top:=0; stack[0]:=n+1; a[n+1]:=a[0];
for i:=n downto 1 do
begin
while (top>0) and (a[stack[top]]>=a[i]) do dec(top);
right[i]:=stack[top]-1;
inc(top); stack[top]:=i;
end;
for i:=1 to n do
begin
tmp:=a[i]*(right[i]-left[i]+1);
if (tmp>lr) or ((tmp=lr) and (left[i]<lu)) then
begin
lr:=tmp;
lu:=left[i];
lv:=right[i];
end;
end;
writeln(lr,' ',lu,' ',lv);
end;
end.