Problem Background

"I realized I shouldn't write music with the expectation that the productivity or achievement will fix my problems, but instead with the hope that my honest expression will move people the way music moves me."

— Robinson in a letter to his fans

Problem Description

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

You have a sequence \( v \) of length \( n \). Each time, you can remove two numbers \( a \) and \( b \), and add \( a - b \) to the sequence. Repeat this operation until only one number remains in the sequence. You need to find the maximum value of this remaining number.

(The coach instantly solved this easy problem, and Mivik was criticized for wasting time on trivial problems)

Input Format

The first line contains a positive integer \( n \), representing the length of the sequence.

The second line contains \( n \) integers, where the \( i \)-th integer \( v_i \) represents the \( i \)-th element of the sequence.

Output Format

A single line containing an integer, representing the maximum value of the remaining number.

Sample Input and Output

Sample Input #1

3
1 2 3

Sample Output #1

4

Sample Input #2

4
-4 5 -2 -3

Sample Output #2

14

Sample Input #3

8
2 0 2 1 0 4 2 3

Sample Output #3

14

Notes

Sample Explanation

Sample 1: First, remove \( 1 \) and \( 2 \), and add \( 1 - 2 = -1 \) to the sequence, resulting in the sequence \([3, -1]\). Then, remove \( 3 \) and \(-1\), and add \( 3 - (-1) = 4 \) to the sequence, leaving only the number \( 4 \). It can be proven that no other operation sequence would result in a larger remaining number.

Data Range

For all data, \( 1 \le n \le 3 \cdot 10^5 \) and \( |v_i| \le 10^9 \).

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

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

Subtask 3 (55 pts): No special restrictions.

见题面 Input 部分

见题面 Output 部分