Pizza
Rodrigo pediu uma pizza de mussarela de N fatias, uma parte somente com cebola e o resto somente com azeitonas. Entretanto, ao receber a pizza em casa, notou que o motoqueiro que a entregou não foi cuidadoso o suficiente, pois tanto as tiras de cebola quanto as azeitonas estavam espalhadas por toda a pizza. Para piorar, como a pizza era de mussarela, as tiras de cebola e as azeitonas estavam grudadas na pizza.
Como gosta mais de cebola do que de azeitona, Rodrigo deseja pegar fatias consecutivas da pizza de tal forma que estas contenham a maior diferença possível entre tiras de cebola e azeitonas. Para isso, ele contou quantas tiras e quantas azeitonas tinham em cada fatia e subtraiu os dois valores, nessa ordem. Assim, sempre que uma fatia contiver mais cebolas que azeitonas, ela recebe um número positivo, e caso contrário, um número negativo. Uma fatia cujo número seja zero contém o mesmo número de tiras de cebolas e azeitonas.
Como Rodrigo não entende de programação, ele resolveu contar com seus serviços.
OBS: repare que é melhor não escolher nenhuma fatia caso somente seja possível escolher fatias consecutivas com mais azeitonas que cebolas.
Tarefa
Escreva um programa que, dados as diferenças entre as quantidades de cebolas e azeitonas em cada fatia de pizza, retorne a maior quantidade possível de cebolas que Rodrigo pode comer a mais do que a quantidade de azeitonas utilizando somente fatias consecutivas de pizza. (lembrando que a primeira fatia é adjacente à última e vice-versa).
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 que indica o número de fatias de pizza (1 ≤ N ≤ 100.000). A segunda linha contém N inteiros K(-100 ≤ K ≤ 100) separados por um espaço em branco com as diferenças entre as quantidades de cebolas e de azeitonas.
Saída
Seu programa deve imprimir, na saída padrão, uma única linha, contendo a maior quantidade de cebolas que Rodrigo pode comer a mais do que azeitonas.
Exemplos
Entrada
6 5 -3 -3 2 -1 3 |
Saída
9 |
Entrada
7 1 -2 2 -1 4 1 -5 |
Saída
6 |
Entrada
2 -3 -10 |
Saída
0 |