Description

Mivik is listening to Nurture, but then the coach walks in, so Mivik pretends to be working on this problem.

You are given a sequence $v$ of length $n$. Each time, you may take out two numbers $a, b$, and add $a-b$ to the sequence. Repeat the operation until only one number remains in the sequence. You need to find the maximum possible value of this remaining number.

(As a result, the coach solved this easy problem at a glance, and Mivik was criticized for doing easy problems for no reason.)

Input Format

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ integers. The $i$-th integer $v_i$ represents the $i$-th element of the sequence.

Output Format

Output one integer in one line, representing the maximum possible value of the final remaining number.

3
1 2 3

4

4
-4 5 -2 -3

14

8
2 0 2 1 0 4 2 3

14

Hint

Sample Explanation

Sample 1: In the first step, take out $1, 2$ and add $1-2=-1$ to the sequence. The sequence becomes $[3,-1]$. Then take out $3, -1$ and add $3-(-1)=4$ to the sequence. Now only one number $4$ remains. It can be proven that there is no sequence of operations that makes the remaining number larger.

Constraints

For all testdata, $1\le n\le 3\cdot 10^5$, $|v_i|\le 10^9$.

Subtask 1 (15 pts): $n\le 3$.

Subtask 2 (30 pts): $v_i\ge 0$.

Subtask 3 (55 pts): No additional constraints.

Input Format

Output Format

Translated by ChatGPT 5