問題文

$N$個の要素からなる正整数列 $a_1,...,a_N$ から $k$ 個( $k\ge 1$ )の要素を選び $b_1,...,b_k$ としたとき,
あなたが得られるスコア $S$ は $k$ 個の要素の中央値 $m$ (後述)を用いて次のように表されます.
$$S=\sum _{i=1}^k(b_i-m)$$ $S$の最大値を求めてください.
なお,答えは必ず整数となることが示せます.整数として出力してください.

※ $k$ 個の数の中央値 $m$ は,これを昇順に並べた数列を $x_1,...,x_k$ としたとき,次のように表されます. $$m=\{\begin{array}{l}{x}_{\frac{k+1}{2}}(k\mathrm{が}\mathrm{奇}\mathrm{数})\\ \frac{1}{2}\times (x_{\frac{k}{2}}+x_{\frac{k}{2}+1})(k\mathrm{が}\mathrm{偶}\mathrm{数})\end{array}$$

入力

$N$
$a_1{a}_2...a_N$

• $1\le N\le 2\times {10}^5$
• $1\le a_i\le {10}^9$
• 入力はすべて整数

出力

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

サンプル

5
1 2 3 4 5

2

4
7 7 7 9

2

10
3 8 9 7 2 2 10 10 35 5

37