FIICode 2025 Qualifying Round - Studenți | Maximize Grandi's Function

Task

We define the function $Grandi(v, n)$ (where $v$ is an array and $n$ is the number of elements of $v$) as follows:

$Grandi(v, n) = \displaystyle \sum_{i=1}^{n}{v_i \cdot (-1)^{i+1}}=v_1-v_2+v_3-v_4+v_5 - \ldots \pm v_n$.

For example: $Grandi([1, 2, 3, 4, 5], 5) = 1 - 2 + 3 - 4 + 5 = 3$.

You are given $n$ and an array $v_1,v_2,\ldots,v_n$. Rearrange the elements of the array $v$ in such a way that $Grandi(v, n)$ is maximized.

Input data

The first line of input contains a single integer $n$ ($1 \le n \le 10^5$) - the length of array $v$.

The second line contains $n$ space separated integers $v_1,v_2,\ldots,v_n$ ($-10^9 \le v_i \le 10^9$) - the elements of array $v$.

Output data

Print a single number, representing the maximum possible value of $Grandi(v, n)$ after optimally rearranging the elements of $v$.

Example 1

stdin

4
5 9 10 2

stdout

12

Explanation

One of the optimal rearrangements of $v$ is $[9,5,10,2]$, as $Grandi([9, 5, 10, 2], 4) = 9 - 5 + 10 - 2 = 12$.

Example 2

stdin

5
3 2 1 4 5

stdout

9

Explanation

One of the optimal rearrangements of $v$ is $[4,1,5,2,3]$, as $Grandi([4, 1, 5, 2, 3], 5) = 4 - 1 + 5 - 2 + 3 = 9$.