绝对值

给定一个长度为 $ n $ 的序列 $ A $

$ [l,r] $ 的价值为 $|\sum_{i=l}^{r} A_i|$, 其中 $|x|$ 表示 $x$ 的绝对值.

令一个数组的权值为划分后的最大价值总和.

对于一个有效划分, 你需要选出 $x_0=0 \leq x_1 < \dots \leq x_k=n$, 并将其分为若干段, 第 $i$ 段区间为 $[x_{i-1}+1, x_i]$.

令 $ ans_i $ 为 $ \set{A_1, \dots, A_i} $ 的权值.

你需要输出 $ \sum_{i=1}^{n} ans_i $ .

第一行一个整数 $ n(1 \leq n \leq 200000) $

第二行 $ n $ 个整数, 第 $ i $ 个数字表示 $ A_i(0 \leq |A_i| < 1048576) $ .

一个整数,表示 $ \sum_{i=1}^{n} ans_i $.

10
-9 -1 -4 0 -7 -8 -4 0 -1 -2

233

2025“钉耙编程”中国大学生算法设计春季联赛 - 热身赛