問題文

Ａ君とＢ君はカードゲームで対戦しています。
ゲームが始まる前には、テーブルの上には $N$ 枚のカードが置かれています。
それぞれのカードには整数が書かれており、$i$ 番目のカードに書かれている整数は $c_i$ です。

ゲームはＡ君が先手で開始され、２人で交互に手番を行っていきます。
手番になったプレイヤーは、テーブルの上から任意に１枚のカードを選んで獲得します。
テーブルの上からカードが無くなったとき、ゲームは終了です。
獲得したカードに書かれている整数の合計が、プレイヤーの「得点」になります。
両プレイヤーは、相手よりも出来るだけ多くの得点を得ることを目指します。

２人にとってこのゲームはあまりに簡単すぎたので、彼らはルールを少し変更することにしました。
獲得したカードの合計値を得点とする代わりに、新しいルールではカードの合計値の絶対値を得点とすることにしました。
つまり、ゲーム終了時にＡ君が獲得しているカードの合計値を $a$ とし、Ｂ君が獲得しているカードの合計値を $b$ とすると、
Ａ君の得点は $|a|$ となり、Ｂ君の得点は $|b|$ となります。

ゲームの「得点差」を $|a| - |b|$ で定義します。ここで定義する「得点差」は負の値にもなりうることに注意してください。
Ａ君は得点差を出来るだけ大きくすることを目指し、Ｂ君は得点差を出来るだけ小さくすることを目指します。
2人が最善の行動をとったときの得点差を出力してください。

入力

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

入力は以下の制約を満たします。
$1 \leq N \leq 10^5$
$0 \leq |c_i| \leq 10^9$
入力値はすべて整数

出力

2人が最善の行動をとったときの得点差を1行に出力してください。 最後に改行してください。

サンプル

3
4 -2 -1

1

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

3