P7917 [Kubic] Addition

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

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.

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

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

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