[Kubic] Addition

建议先看 B 题题目背景。

有一个初始长度为 $n$ 的序列 $a$。你需要进行 $n-1$ 次操作。每一次操作先在当前序列中选出两个相邻的数 $x,y$ 并删除（原序列中 $x$ 在 $y$ 左边），再往原位置插入一个 $x+y$ 或一个 $x-y$。$n-1$ 次操作之后最终只会剩下恰好一个数，求这个剩下的数的最大值。

第一行，一个整数 $n$。 第二行，共 $n$ 个整数 $i$ 个表示 $a_i$。

共一行，一个整数，表示答案。

5
-1 1 1 -1 1

3

对于 $100\%$ 的数据，$1\le n\le 10^5,|a_i|\le 10^9$。 ||分值|$n$|$\vert a_i\vert$|特殊性质| |:-:|:-:|:-:|:-:|:-:| |$\operatorname{Subtask}1$|$10$|$\le 2$|无特殊限制|无| |$\operatorname{Subtask}2$|$20$|$\le 100$|无特殊限制|无| |$\operatorname{Subtask}3$|$5$|无特殊限制|无特殊限制|$a_i\ge 0$| |$\operatorname{Subtask}4$|$30$|无特殊限制|$\le 1$|无| |$\operatorname{Subtask}5$|$35$|无特殊限制|无特殊限制|无| ### 样例解释 一种操作过程如下： `-1 1 1 -1 1` `-1 1 1 -2` `-1 1 3` `-1 4` `3` 可以证明没有更优的方案。