beecrowd | 3095

Warriors' Pudding

By Ygor Ribeiro, IFSULDEMINAS Brazil

Timelimit: 1

As everyone knows, Bills, one of the gods of Dragon Ball Super, loves pudding. In the movie "Dragon Ball Z: The Battle of the Gods", Majin Boo and Bills fought over a pudding. Almost the land went up because of that, but Bulma thought of something to please both of them and also Goku, who loves a good dessert. Bulma has a row with N baskets, each of these baskets has a number of puddings.

Let's define how the division between the 3 warriors will work. Bulma said that the amount of puddings will be divided as follows: The baskets are arranged randomly on the table, first the Ci basket, then the Ci + 1, until the Cnth basket, for all 1 <= i <= N.

Let PB be the sum of Bills' puddings, PG be the sum of Goku's puddings and PM the sum of Majin Boo's puddings. For there to be no more confusion, PB has to be equal to PM and both were satisfied with the equality. This equality needs to be as great as possible. Therefore, PG is equal to Ptotal - (PB + PM). Initially all sums are 0.

Division restrictions: Bills is very brown and bossy so he said he would only accept such division if the baskets with puddings he would take were a continuous segment and he would have to take the first basket, that is, a continuous segment starting at the first. It doesn’t end there, he said that Majin Boo would also have to keep a continuous segment of baskets but start with the last one and start taking the previous ones. It is not possible for both to take the same basket.

Example: Baskets with {1, 3, 2, 1, 4} puddings in each, respectively. The amount of Pudding that Bills and Majin Boo would have at the end of the division following the restrictions would be 4 Puddings. Bills would take the first 2 baskets [1, 3], Majin Boo with the last basket only [4]. Both totaling 4 puddings. Goku will have the third and fourth basket, totaling 3 puddings for him. Note that this is the only way for Bills and Majin Boo to have the same amount of pudding following the restrictions imposed by Bills. Goku doesn't care about keeping the smallest amount.

Input

A primeira linha de entrada contém um inteiro N (1 <= N <= 100000) que representa o número de cestas. A próxima linha contém N inteiros Pi (1 <= Pi <= 10^8), representando a quantidade de pudins na cesta i (1 <= i <= N).

Output

The exit should be the largest amount of puddings that Bills and Majin Boo will receive following the restrictions of the problem.

 Input Samples Output Samples 5 1 3 2 1 4 4
 4 1 5 6 8 0