A134862.午枫的课堂笔记

小午在课堂上按顺序记录 $N$ 个数，第 $i$ 个数为 $A_i$。他手上有一块“笔记板”，一开始是空的。对于每一个 $i = 1,2,\dots,N$，小午需要恰好选择一种操作：

• 将数字 $A_i$ 写到笔记板的末尾；
• 擦掉笔记板末尾的一个数字（如果当前笔记板为空，则不能进行此操作）。

所有操作完成后，笔记板中剩余的一串数字的和就是本次结果。小午希望通过合理选择每一步操作，使最终剩余数字的总和尽可能大。请你输出这个最大可能值。

第一行输入一个整数 $N$，表示数字个数。

第二行输入 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示按顺序记录的数字。

输出一个整数，表示所有操作结束后，笔记板中数字总和的最大可能值。

【解释说明】

一种最优操作方式如下：

写入 3 → [3]

写入 -1 → [3, -1]

删除末尾 → [3]

写入 5 → [3, 5]

写入 -9 → [3, 5, -9]

删除末尾 → [3, 5]

最终剩余元素为：3,5

总和为 $8$，这是最大值。

【数据范围】

对于 $100\%$ 的测试数据，满足：

$1 \le N \le 2 \times 10^5$

$-10^9 \le A_i \le 10^9$