粒子合并 (unite)

• 输入：unite.in
• 输出：unite.out
• 时间限制：1 s
• 内存限制：128 MB

题目描述

一条直线上有 $n$ 个粒子，从左到右编号为 $1$ 到 $n$。第 $i$ 个粒子的电荷为 $c_i$，电荷可以为负数、零或正数。

你有一台粒子合并装置。每次操作可以选择一个还存在的粒子并将它移除。移除后，剩下的粒子会向中间靠拢：

• 如果被移除粒子的左右两侧都存在粒子，且它们的电荷分别为 $x$ 和 $y$，那么这两个相邻粒子会合并成一个电荷为 $x+y$ 的新粒子。
• 如果被移除粒子只有一侧存在粒子，则不会发生合并。

例如，电荷序列为 $[-3,1,4,-1,5,-9]$。若移除第 $4$ 个粒子，左右两侧电荷为 $4$ 和 $5$ 的粒子会合并，序列变为 $[-3,1,9,-9]$。

若再移除当前序列中的第 $1$ 个粒子，序列变为 $[1,9,-9]$。

你需要不断操作，直到只剩下一个粒子。请问最终剩余粒子的最大可能电荷是多少。

输入格式

从文件 unite.in 中读入数据。

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $c_1,c_2,\dots,c_n$，表示每个粒子的初始电荷。

输出格式

输出到文件 unite.out 中。

输出一个整数，表示最终剩余粒子的最大可能电荷。

注意，答案可能超过 $32$ 位整数范围。

样例1输入

6
-3 1 4 -1 5 -9

样例1输出

9

样例1解释

一种最优操作方式为：

• 先移除电荷为 $-1$ 的粒子，序列变为 $[-3,1,9,-9]$。
• 再移除最左侧电荷为 $-3$ 的粒子，序列变为 $[1,9,-9]$。
• 接着移除电荷为 $-9$ 的粒子，序列变为 $[1,9]$。
• 最后移除电荷为 $1$ 的粒子，剩余粒子的电荷为 $9$。

可以证明最终剩余粒子的电荷不可能超过 $9$。

数据范围

对于所有数据，$1 <= n <= 200000$，$-10^9 <= c_i <= 10^9$。每个测试点 $10$ 分。