Problem Statement

A and B are playing a card game against each other.
Before the game starts, $N$ cards are placed on the table.
Each card has an integer written on it, and the integer written on the $i$-th card is $c_i$.

A moves first, and the two players take turns alternately.
The player whose turn it is chooses any one card from the table and takes it.
The game ends when there are no cards left on the table.
The sum of the integers written on the cards a player has taken becomes that player's "score".
Both players aim to get as many more points than the opponent as possible.

This game was far too easy for the two of them, so they decided to change the rules slightly.
Instead of using the sum of the taken cards as the score, the new rule uses the absolute value of the sum of the cards as the score.
That is, letting $a$ be the sum of the cards A has taken at the end of the game and $b$ be the sum of the cards B has taken at the end of the game,
A's score is $|a|$ and B's score is $|b|$.

The "score difference" of the game is defined as $|a| - |b|$. Note that the "score difference" defined here can be negative.
A aims to make the score difference as large as possible, and B aims to make the score difference as small as possible.
Output the score difference when both players play optimally.

Input

$N$
$c_1\ c_2\ \ldots\ c_N$

The input satisfies the following constraints.
$1 \leq N \leq 10^5$
$0 \leq |c_i| \leq 10^9$
All input values are integers.

Output

Output the score difference when both players play optimally, on one line. Print a newline at the end.

Sample

3
4 -2 -1

1

8
3 -1 4 -1 5 -9 2 -6

3