时间限制： 1.0 秒

空间限制： 512 MB

题目描述

过去有一个项链。这个项链上串了 $N$ 个珠子，其中第 $i$ 个珠子上有 $a_i$ 的能量值（$a_i$ 不一定非负）。

对于一段连续的珠子，过去定义其美丽程度为它们的能量值之和。自然地，一个项链的美观值定义为它的所有非空连续子段的美丽程度的最大值。

过去得到了一把神奇剪刀，他可以把这个项链的恰好一个连续子段剪下来，然后翻转这个子段，再拼接回去得到一个新项链。

过去想利用这把剪刀，得到一个美观值尽可能大的新项链。那么问题来了：请你告诉过去，他的新项链的美观值最大可以是多少。

输入格式

从标准输入读入数据。

输入第一行包含一个正整数 $N$，保证 $1 \le N \le 2 \times 10^5$。

接下来一行 $N$ 个整数，描述序列 $a_i$，这里下标从 $1$ 开始，保证 $a_i$ 的绝对值不超过 $10^8$。

输出格式

输出到标准输出。

输出包含一行。

第一行包含一个整数，表示美观值的最大值。

6
3 2 -1 1 -1 5

11

样例 1 解释

翻转 $a_3, a_4$ 之后，美丽程度的最大值在子段 $[5, 3, 2, 1]$ 上取到，故答案为 $11$。

子任务

对于所有数据，保证 $N\le 2\times 10^5$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。