Problem Statement

When you choose $k$ elements ( $k \ge 1$ ) from a sequence of positive integers $a_1,...,a_N$ consisting of $N$ elements and call them $b_1,...,b_k$,
the score $S$ you obtain is expressed as follows, using the median $m$ (described below) of the $k$ elements.
\[ S = \sum_{i=1}^{k} (b_i - m) \] Find the maximum value of $S$.
It can be shown that the answer is always an integer. Output it as an integer.

Note: The median $m$ of $k$ numbers is expressed as follows, where $x_1,...,x_k$ is the sequence obtained by sorting them in ascending order. \[ 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} \]

Input

$N$
$a_1\ a_2\ ...\ a_N$

• $1 \le N \le 2\times 10^5$
• $1 \le a_i \le 10^9 $
• All inputs are integers.

Output

Output the answer.
Print a newline at the end.

Sample

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