CF1038D Slime

有 $n$ 只史莱姆，每只史莱姆有一个分数，每次一只史莱姆可以吞掉左边的或者右边的相邻史莱姆（要是有的话），然后它的分数会减去被吞的史莱姆的分数，问最后剩下的史莱姆分数最大为多少。

第一行一个整数 $n$。 第二行 $n$个整数，表示史莱姆的分数。

一个整数，即最大分数。

$1 \le n \le 500\,000, -10^9 \le a_i \le 10^9$，其中 $a_i$ 是 $i$ 个史莱姆的分数。