题目描述

航空引擎涡轮叶片是确保国家空天安全的核心装备，其制造工艺代表了工业技术的巅峰。

这天，在精密检测实验室的中央，首席结构分析师小蓝正利用高精度传感器，沿涡轮叶片的中轴线进行连续扫描。扫描产生的反馈数据被转化为一条包含 $N$ 个元素的序列 $A = (A_1, A_2, \dots, A_N)$。

为了评估叶片在极限运行负载下的稳定性，小蓝需要针对这组序列计算出一个综合应变指标。计算该指标的第一步是选定三个分割点 $i, j, k$（满足 $1 \le i < j < k < N$），将整条序列划分为以下四个连续且非空的子段：

1. 第一段：$A_1, \dots, A_i$；
2. 第二段：$A_{i+1}, \dots, A_j$；
3. 第三段：$A_{j+1}, \dots, A_k$；
4. 第四段：$A_{k+1}, \dots, A_N$。

第二步，需要计算每一个子段内所有数值的总和，并取其绝对值。这四个绝对值的累加总和被定义为该划分方案下的综合应变指标：

$$|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|$$

分割点的选择有多种可能，不同的方案会导致不同的指标结果。

现在，请你帮助小蓝找出一种划分方案，使得得到的综合应变指标的数值最大。

输入格式

第一行包含一个正整数 $N$，表示扫描序列采集到的反馈节点总数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示序列的元素。

输出格式

输出一行一个整数，表示序列所能达到的最大综合应变指标。

5
1 -1 -2 3 5

12

提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$4 \le N \le 100$；

对于 $60\%$ 的评测用例，$4 \le N \le 400$；

对于所有评测用例，$4 \le N \le 10^5$，$-10^9 \le A_i \le 10^9$。