Maximum Final Value from Sequence Operations

Mivik is listening to Nurture when the coach walked in, so he pretended he was solving this problem.

You are given a sequence \(v\) of length \(n\). In each operation, you may remove two numbers \(a\) and \(b\) from the sequence and then add \(a-b\) to the sequence. You repeat this process until only one number remains. Your task is to compute the maximum possible value of the final number.

Observation: By carefully arranging the order of operations, one optimal strategy is to choose an ordering that leads to the expression \[ v_{i_1} - (v_{i_2} - v_{i_3} - \cdots - v_{i_n}) = \Bigl(\sum_{i=1}^{n} v_i\Bigr) - 2\min(v), \] which is maximum when \(\min(v)\) is subtracted twice.

(Mivik later got criticized for wasting time on this trivial problem.)

inputFormat

The first line contains a single integer \(n\) (\(2 \le n \le 10^5\)), the length of the sequence.

The second line contains \(n\) space-separated integers \(v_1, v_2, \dots, v_n\).

outputFormat

Output a single integer, the maximum possible final number obtainable after applying the operations.

sample

2
1 5

4