Background

It is recommended to read the background of Problem B first.

Problem Description

There is an initial sequence $a$ of length $n$. You need to perform $n - 1$ operations. In each operation, you first choose two adjacent numbers $x, y$ in the current sequence and delete them ($x$ is to the left of $y$ in the original sequence), then insert either $x + y$ or $x - y$ at the original position. After $n - 1$ operations, exactly one number will remain. Find the maximum possible value of this remaining number.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers, where the $i$-th integer represents $a_i$.

Output Format

Output a single line containing one integer, which is the answer.

5
-1 1 1 -1 1

3

Hint

For $100\%$ of the testdata, $1 \le n \le 10^5, |a_i| \le 10^9$.

| |Score|$n$|$|a_i|$|Special Property| |:-:|:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$10$|$\le 2$|No special restrictions|None| |$\operatorname{Subtask}2$|$20$|$\le 100$|No special restrictions|None| |$\operatorname{Subtask}3$|$5$|No special restrictions|No special restrictions|$a_i \ge 0$| |$\operatorname{Subtask}4$|$30$|No special restrictions|$\le 1$|None| |$\operatorname{Subtask}5$|$35$|No special restrictions|No special restrictions|None|

Sample Explanation

One possible sequence of operations is as follows:

-1 1 1 -1 1

-1 1 1 -2

-1 1 3

-1 4

3

It can be proven that there is no better plan.

Input Format

Output Format

Translated by ChatGPT 5