# Banks

Time Limit: 10 Seconds Memory Limit: 131072 KB

On Wall Street from Wonderland, we have n banks, with 10000 > n > 0. Each bank has exactly two neighbours, the left (L) and right (R) neighbour. The first bank’s left neighbour is the last bank, while the last bank’s right neighbour is the first bank. Each bank i(n>i≥0) has a capital k_{i }with 32000>k_{i }>-32000. The entire capital of all banks put together is known to be positive. Whenever some capital k_{i }of bank i is negative, the Bank Fairy can do a magic move and turn the capital into a positive one. For instance, if k_{i}=-7, after the magic move, k_{i }=7. Unfortunately, the magic move has consequences for both neighbours of bank i. Each sees its capital reduced with the absolute value of the capital of bank i. For instance if bank L has capital k_{L }=5 and bank R has capital k_{R }=11, then after the magic move k_{L }=-2 and k_{R}=4.

Which is the minimal number of magic moves which the Bank Fairy has to do in order to make the capital of all banks greater than or equal to 0?

## Input

On the first input line, we have the number n of banks. On the second input line, we have the capitals k_{i}(n>i≥0) of all banks, in the order in which they are found on Wall Street from Wonderland. Each capital is separated by a single whitespace from the next one, except for the final capital which is directly followed by the newline character.

## Output

The output contains a single line with the value of the minimal number of magic moves.

## Sample Input

4 1 -2 -1 3

## Sample Output

9Submit