In an RPG, there are typically several stats that contribute to a level. In the RPG we're in, we factor in the experience killed from monsters. On the other hand, this is a slightly different RPG than the typical; the monsters can kill other monsters.

There are ~n~ monsters in a row, each having an integer value, denoting the amount of EXP you are able to gain from it.

Any monster can kill its adjacent monster (the closest monster to its left or right, assuming that the monster is still alive).

When a monster with EXP ~x~ kills a monster with EXP ~y~, the amount of EXP the remaining monster has changes from ~x~ to ~x - y~.

The monsters will kill each other until there is one left, which you will kill to gain EXP.

Find the maximum possible value of the last monster.

Note: Please use fast I/O for this problem, or it is difficult to pass in languages like Java.

Input Specification

The first line of input will contain ~n~ ~(1 \le n \le 5 \times 10^5)~, the number of monsters that exist.

The next line contains ~n~ integers ~v_i~ ~(-10^9 \le v_i \le 10^9)~, the amount of EXP the ~i~-th monster has.

Output Specification

Print a single integer - the maximum possible value of the last monster.

Sample Input 1

4
2 1 2 1

Sample Output 1

4

Sample Input 2

5
0 -1 -1 -1 -1

Sample Output 2

4

Sample Explanation

In the first sample, a possible way of getting the monster with a maximum value of ~4~ is:

• Second monster kills the third, changing the input to 2, -1, 1,
• Second monster kills the third, changing the input to 2, -2,
• First monster kills the second, changing the input to 4.

In the second sample, the first monster can continuously kill the monsters to its right, resulting in a value of ~4~.