Maximum Final Value

You are given a sequence of n integers \(a_1,a_2,\dots,a_n\). You are allowed to perform exactly \(n-1\) operations. In each operation, you must choose two adjacent numbers \(x\) and \(y\) (with \(x\) to the left of \(y\)) from the current sequence, remove them, and then insert either \(x+y\) or \(x-y\) in their place.

After performing \(n-1\) operations, only one number remains. Your task is to determine the maximum possible value of this final number.

Observation: It can be shown that the maximum final value is obtained by choosing the operations so that the final answer is \(a_1 + \sum_{i=2}^{n} |a_i|\). In the case where \(n = 1\), the answer is simply \(a_1\).

inputFormat

The first line contains an integer \(n\) (\(1 \le n \le 10^5\)), representing the length of the sequence.

The second line contains \(n\) space-separated integers \(a_1, a_2, \dots, a_n\), which are the elements of the sequence.

outputFormat

Output a single integer — the maximum possible final value after performing \(n-1\) operations.

sample

2
1 2

3