配点 : 300点

問題文

長さ $N$ の正数列 $A$ があり、$i(1≦i≦N)$ 番目の要素は $A_i$ です。
くしらくんは $A$ の空ではない部分列 $B$ を自由に選びます。

• $\mathrm{sum}(B) - |\mathrm{max}(B) - \mathrm{min}(B)|$

をスコアと定めたときの、スコアの最大値を答えてください。

ただし、数列 $X$ に対して、$\mathrm{sum}(X), \mathrm{max}(X), \mathrm{min}(X)$ を以下のように定めます。

• $\mathrm{sum}(X) := (数列 X の要素の総和)$
• $\mathrm{max}(X) := (数列 X の要素の最大値)$
• $\mathrm{min}(X) := (数列 X の要素の最小値)$

制約

• $1≦N≦2×10^5$
• $0≦A_i≦10^9$
• 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

出力

答えを出力してください。

入出力例1

4
3 5 1 2

7

$3, 5, 2$ を選ぶとスコアは $7=(10-(5-2))$ となり最大です。

入出力例2

3
1 10 100

100

入出力例3

5
0 0 0 0 0

0

どのように選んでもスコアは変わりません。