問題文

$N$ 個の整数があります。$i$ 番目の整数は $A_i$ です。$\mathrm{First}$ 君と $\mathrm{Second}$ 君が交互に $1$ 回ずつ以下の操作を行います。

• 整数を $1$ つ選び、それを削除する。その後、残っている整数を全て $-1$ 倍する。

$\mathrm{First}$ 君が先手で、整数が全て削除されたら終了します。

$\mathrm{First}$ 君が削除した整数の和を $X$ 、 $\mathrm{Second}$ 君が削除した整数の和を $Y$ とします。$\mathrm{First}$ 君は $X-Y$ を最大化したいですが、 $\mathrm{Second}$ 君は $X-Y$ を最小化したいです。

両者が最善を尽くしたときの最終的な $X-Y$ を求めてください。

入力

$N$
$A_1$ $A_2$ $\cdots$ $A_N$

• $1 \leq N \leq 2 \times 10^5$
• $|A_i| \leq 10^9$ $(1 \leq i \leq N)$
• 入力は全て整数

出力

両者が最善を尽くしたときの最終的な $X-Y$ を整数で出力してください。

サンプル

3
-1 4 -2

1

14
-523328364 -409607197 -712671537 -766381325 472867409 -811025573 -971818355 -66399298 633965694 -22544287 -720923839 -905888279 514666353 -359356404

-4648445002