KAGAIN - Chiến trường Ô qua
Tác giả: ll931110
Ngôn ngữ: Pascal
Program KAGAIN;
Const
input = '';
output = '';
Var
a,left,right,stack: array[1..30000] of longint;
t,n,i,top: longint;
fi,fo: text;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Procedure closefile;
Begin
Close(fo);
Close(fi);
End;
Procedure push(x: longint);
Begin
inc(top);
stack[top]:= x;
End;
Procedure solveleft;
Var
i: longint;
Begin
top:= 1;
stack[top]:= 1;
left[1]:= 1;
For i:= 2 to n do
Begin
While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
If top = 0 then left[i]:= 1 else left[i]:= stack[top] + 1;
push(i);
End;
End;
Procedure solveright;
Var
i: longint;
Begin
top:= 1;
stack[top]:= n;
right[n]:= n;
For i:= n - 1 downto 1 do
Begin
While (top > 0) and (a[stack[top]] >= a[i]) do dec(top);
If top = 0 then right[i]:= n else right[i]:= stack[top] - 1;
push(i);
End;
End;
Procedure solve;
Var
kq,i,x,y: longint;
Begin
Readln(fi, n);
For i:= 1 to n do read(fi, a[i]);
Readln(fi);
solveleft;
solveright;
x:= left[1];
y:= right[1];
kq:= (y - x + 1) * a[1];
For i:= 2 to n do
if kq < (right[i] - left[i] + 1) * a[i] then
Begin
kq:= (right[i] - left[i] + 1) * a[i];
x:= left[i];
y:= right[i];
End;
Writeln(fo, kq, ' ', x, ' ', y);
End;
Begin
openfile;
Readln(fi, t);
For i:= 1 to t do solve;
closefile;
End.