XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: acoes.x, onde x deve ser c, cpp, java, js ou py

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.
Por exemplo, suponha que as variações do preço das ações sejam:
  • 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%
Se aplicarmos R$ 100 no dia 1, ao final do dia 4 vamos ter uma variação de 3+1-2-3 = -1, ou seja, prejuízo de R$ 1. Mas se começarmos aplicando no dia 2, ao final teremos uma variação de 1-2-3+5 = 1%, ou seja, lucro de R$ 1. Juninho, que além de inteligente é também vidente (ou seja, consegue prever o futuro), pediu a sua ajuda para descobrir qual é a maior quantidade de dinheiro que ele pode lucrar investindo exatamente R$ 100,00 durante quatro dias. Para isso, ele vai te dizer a variação das ações nos próximos N dias seguidos, onde N ≥ 4.

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 Xi, separados por espaços em branco, sendo Xi 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 ≤ 105
  • -1000 ≤ Xi ≤ 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

Entrada
5
3 1 -2 -3 5 
Saída
1
Entrada
6
-2 1 -2 1 0 -3
Saída
0
Entrada
8
-1 -2 -3 -4 -5 -6 -7 -8
Saída
-10
Tarefas Programação Nível Júnior
Promoção
logo sbc
Patrocínio
Apoio
Coordenação