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

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

Corredor

Bruninho está programando um personagem virtual para o próximo desafio de um jogo de aventura em que, numa das fases, o personagem tem que entrar em um corredor, percorrer algumas salas e depois sair do corredor. Ele pode entrar apenas uma vez, e passar por cada sala apenas uma vez. Todas as salas possuem uma porta de entrada e uma de saída, como ilustra a parte (a) da figura abaixo. Ao passar por uma sala o jogador ganha um certo número de vidas (que pode ser negativo!). O objetivo é passar pelo corredor coletando a maior quantidade possível de vidas! Por sorte, sempre existe ao menos uma sala onde se ganha um número positivo de vidas.

No exemplo acima, o personagem de Bruninho pode ganhar, no máximo, 12 vidas, por exemplo, entrando pela sala 2 e saindo pela sala 4, como mostrado na parte (b) da figura. Nesta tarefa, você deve escrever um programa que, dados os números de vidas correspondentes a cada sala do corredor, calcule a quantidade máxima de vidas que será possível ganhar.

Entrada

A entrada é composta por duas linhas. A primeira linha contém um inteiro N, o número de salas no corredor. A segunda linha contém N números inteiros, positivos ou negativos, indicando a quantidade de vidas que se ganha em cada sala.

Saída

Seu programa deve imprimir uma linha, com o número máximo de vidas que é possível ganhar.

Restrições

  • 1 ≤ N ≤ 50000; e o número de vidas nas salas está entre -100 e 100

Informações sobre a Pontuação

  • Em um conjunto de casos de teste totalizando 30 pontos, N ≤ 1000

Exemplos

Entrada
7
-2 5 -1 8 -11 7 3
Saída
12
	
Entrada
10
50 42 -35 2 -60 5 30 -1 40 31
Saída
105
	
Tarefas Programação Nível 1
Promoção
logo sbc
Patrocínio
Apoio
Coordenação