Ações da bolsa

Juninho é um menino muito visionário e inteligente, que quer ficar rico. Aos 12 anos de idade, já está interessado em investimentos de ações na bolsa de valores. Uma ação é como se fosse um pedaço de uma empresa que qualquer pessoa pode comprar. E como cada empresa tem tamanhos e valores diferentes, cada ação também tem diferentes valores, e esses valores mudam o tempo todo. Suponha, por exemplo, que Juninho compre uma ação de uma empresa de petróleo, que custe R$ 100. Suponha que no dia seguinte, essa empresa descubra um enorme poço de petróleo, o que vai dar muitos lucros para ela no futuro. Essa empresa, então, passa a ser mais valorizada, e conseqüentemente o preço das ações sobem. Suponha que as ações subiram 20% nesse dia. Então Juninho, que tinha uma ação de R$ 100, hoje tem a mesma ação, mas que vale R$ 120. Ou seja, se ele a vender hoje, vai ter um lucro de R$ 20, só por ter comprado e vendido a ação. Uma empresa de refrigerantes criou um novo tipo de investimento especial para iniciantes. Ela ocorre da seguinte maneira:

• O investidor compra as ações da empresa na manhã do dia X;
• O dinheiro fica investido durante exatamente quatro dias seguidos;
• Ao final dos quatro dias, são aplicados juros simples ao preço das ações; todas elas são vendidas e o dinheiro é dado de volta ao investidor.

• Dia 1: Aumento de 3%
• Dia 2: Aumento de 1%
• Dia 3: Queda de 2%
• Dia 4: Queda de 3%
• Dia 5: Aumento de 5%
• Dia 6: Queda de 5%

Entrada

A entrada é composta por duas linhas. Na primeira, é dado um número inteiro N, indicando a quantidade de dias que Juninho já sabe qual será a variação do valor da ação. Na segunda linha são dados N números inteiros X_i, separados por espaços em branco, sendo X_i a variação do preço das ações no dia i.

Saída

Seu programa deve imprimir na saída padrão uma única linha, contendo um número inteiro indicando qual é o maior lucro que Juninho pode conseguir ao investir nos dias que ele previu (o dinheiro não pode ficar investido em nenhum dia que ele não previu). Note que o `lucro" pode na verdade ser prejuízo (lucro negativo), se as ações se desvalorizarem.

Restrições

• 4 ≤ N ≤ 10⁵
• -1000 ≤ X_i ≤ 1000

Informações sobre a pontuação

• Em um conjunto de casos de teste que totaliza 30 pontos, N ≤ 10 e $0 ≤ X_i ≤ 100.
• Em um conjunto de casos de teste que totaliza 55 pontos, N ≤ 100 e -100 ≤ X_i ≤ 100.

Exemplos

5
3 1 -2 -3 5 

1

6
-2 1 -2 1 0 -3

0

8
-1 -2 -3 -4 -5 -6 -7 -8

-10