题目背景

你在玩物理画线。

题目描述

有 $N$ 个球和 $N$ 个杯子，从左到右编号依次为 $1\dots N$。开始时第 $i$ 个球对准第 $i$ 个杯子（不受影响的情况下第 $i$ 个球落入第 $i$ 个杯子）。第 $i$ 个杯子有一个分值 $c_i$，一个球落入一个杯子可以获得该杯子的分数（杯子容量视为无限），分数可能为负数。

你可以画两种线，线的两端点必须对准某个杯子，且两个端点不能是同一个杯子：

1. 从左上到右下，设左上对准的杯子编号为 $i$，右下对准的杯子编号为 $j$，使编号为 $i\dots j$ 的球全部落入第 $j$ 号杯子。

2. 从右上到左下，设左下对准的杯子编号为 $i$，右上对准的杯子编号为 $j$，使编号为 $i\dots j$ 的球全部落入第 $i$ 号杯子。

现在你想知道你只用恰好一根第一种线、恰好一根第二种线，分别能获得的最大分数。

输入格式

输入的第一行包含一个整数 $N$。

接下来一行 $N$ 个整数，表示 $c_1\dots c_N$。

输出格式

输出第一行一个整数——只使用第一种的最大分数。

输出第二行一个整数——只使用第二种的最大分数。

6
6 10 -7 2 5 -12

19
56

提示

数据范围：

Subtask#0 为样例。

$3\le N\le3\times10^5$，$|c_i|\le10^9$。

样例解释：

第一幅图为第一种线，分数：$6+10+5+5+5+(-12)=19$，可以证明是最大值。

第二幅图为第二种线，分数：$6+10+10+10+10+10=56$，可以证明是最大值。