問題文

テーブルの上に $N$ 個の整数が左右一列に並んでいます。 あなたはこれから以下の操作を $0$ 回以上の好きな回数行います。

• 整数 $l,r\ (1 \le l \le r \le N)$ を選ぶ。テーブルの左から $l,l+1,\dots,r$ 番目の整数を全てそれらの最大値に置き換える。

操作後の各整数の絶対値の総和としてあり得る最大値を求めてください。

入力

$N$
$A_1$ $A_2$ $\dots$ $A_N$

$1$ 行目にはテーブルの上に並んでいる整数の個数 $N$ が与えられる。$N$ は $1 \le N \le 200000$ を満たす。

$2$ 行目にはテーブルの上に並んでいる $N$ 個の整数 $A_1,A_2,\dots,A_N$ が半角空白で区切られて与えられる。各 $A_i$ は $-1000000000 \le A_i \le 1000000000$ を満たす。

出力

答えを出力し、最後に改行してください。

サンプル

4
2 -2 1 -3

9