問題文

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

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

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

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

入力

$N$
$c_1{c}_2\dots c_N$

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

出力

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

サンプル

3
4 -2 -1

1

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

3