题目描述

给定 $n$ 个数 $A[1..n]$。有两种操作：

• 操作一：对于某对 $(i,j)$，$(i<j)$，把 $A[i..j]$ 变成 $A[j]$。
• 操作二：对于某对 $(i,j)$，$(i<j)$，把 $A[i..j]$ 变成 $A[i]$。

计算只使用一次操作一和只使用一次操作二的两种情况下， $\displaystyle \sum_{i=1}^{i \leq n} A[i]$ 的最大值。

输入格式

第一行一个数 $n$。 接下来 $n$ 个数表示 $A[1..n]$。

输出格式

两个数，分别表示只使用一次操作一和只使用一次操作二的两种情况下，$\displaystyle \sum_{i=1}^{i \leq n} A[i]$ 的最大值。

样例输入

6
6 10 -7 2 5 -12

样例输出

19
56

提示

操作1取 $i=3,j=5$;

操作2取 $i=2,j=6$。

数据规模与约定

对于 $100\%$ 的数据，$n\leq 3\times 10^5$。

题目来源

Dragonite提供翻译