Problema A - Publicidade

Exemplo Uma empresa pretende construir um painel rectangular gigante de publicidade numa rua muito movimentada. Para ter a maior vantagem possível sobre a concorrência o painel deve ser o maior possível, ou seja, possuir a maior área (visto que os negócios têm corrido bem, o dinheiro não é problema).

Como a empresa não está interessada em ter o painel arrancado pela mais pequena rajada de vento, este deve possuir um ponto de apoio por todo o painel. Isto é, qualquer que seja o ponto do painel, atrás deste deve existir um edifício.

Problema

Dado as descrições das alturas dos prédios de uma rua, determinar a maior área para o painel rectangular de publicidade, sabendo que cada prédio tem largura de uma unidade.

Input

Na primeira linha vem o inteiro N (1 <= N <= 100000), indicando o número de prédios a considerar. Seguem-se N linhas com inteiros não negativos e menores ou iguais a 10000 que indicam as alturas dos prédios por ordem, da esquerda para a direita.

Output

Uma única linha com um inteiro não negativo com o valor da área máxima que é possível conseguir.

Exemplo de Input

16
0
1
2
5
4
2
6
0
2
1
3
0
1
2
3
0

Exemplo de Output

10
 O exemplo dado corresponde à imagem inicial.

A imagem em baixo indica onde deveria ficar colocado o painel publicitário.
Final Nacional das ONI'2006
Departamento de Ciência de Computadores
Faculdade de Ciências da Universidade do Porto
(19 de Maio de 2006)