SPOJ Brasil

A Sociedade dos Bairros de Campinas (SBC) está revitalizando as ruas da cidade. Muitas ruas são decoradas por árvores igualmente espaçadas ao longo da calçada; além de oferecer sombra durante dias ensolarados, elas mantem Campinas sempre fresca, como gostam seus habitantes.

Por razões estéticas, a SBC quer podar as árvores de cada rua de forma que suas copas estejam todas em uma mesma linha reta (não necessariamente paralela ao chão). Se necessário, a SBC pode arrancar a primeira ou a última árvore da rua; neste caso, a jardineira da árvore arrancada deve estar alinhada com as copas das outras árvores.

No entanto, a prefeitura de Campinas se opôs ao plano baseada na legislação ambiental da cidade. Depois de vários meses de negociação, a SBC e a prefeitura chegaram a um acordo: o projeto poderia seguir em frente contanto que a sociedade se comprometesse a maximizar a soma das alturas restantes das árvores.

Por exemplo, se uma rua tem quatro árvores de alturas 1m, 2m, 4m e 6m, conforme a figura abaixo, um plano é fazer a poda de forma que as árvores tenham alturas 1m, 2m, 3m e 4m, para uma soma total de 10m. No entanto, se arrancarmos a primeira árvore, teríamos árvores com alturas de 0m, 2m, 4m e 6m, para uma soma total de 12m, que é o valor máximo neste caso.

Tarefa

Como Campinas tem muitas avenidas de mão dupla cortando os dois lados da cidade, a SBC não conseguiu determinar projetos ótimos para todas as vias da metrópole. Por isso, eles pediram que você escrevesse um programa que determina a maior soma total das alturas de árvores para uma determinada rua.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N (3 ≤ N ≤ 3 × 10⁴), representando o número de árvores na rua. Cada uma das N linhas seguintes contém um número Hi (0.01 ≤ Hi ≤ 100.00), indicando a altura da i-ésima árvore em metros; todas as alturas são dadas com dois algarismos decimais (ou seja, com precisão de centímetros).

Saída

Seu programa deve imprimir, na saída padrão, um único número indicando a soma total máxima das árvores em metros, com dois algarismos decimais (ou seja, com precisão de centímetros).

Exemplo

Entrada:
4
1.00
2.00
4.00
6.00

Saída:
12.00

Entrada:
6
1.23
0.07
3.45
4.56
0.07
6.78

Saída:
0.42