問題文

$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{cases} \ x_{\frac{k+1}{2}} \ (kが奇数) \\ \ \frac{1}{2} \times (x_{\frac{k}{2}} + x_{\frac{k}{2} +1 }) \ (kが偶数) \end{cases} \]

入力

$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