[Balkan2012]balls

时间限制:2s      空间限制:128MB

题目描述

给定N个数A[1..n]。有两种操作:
操作1:对于某对(i,j)(i<j),把A[i..j]变成A[j]。
操作2:对于某对(i,j)(i<j),把A[i..j]变成A[i]。
计算只使用一次操作1和只使用一次操作2的两种情况下,sum(A[1..n])的和的最大值。


输入格式

第一行一个数N,N<=300000
接下来N个数表示A[1..n]


输出格式

两个数,分别表示只使用一次操作1和只使用一次操作2的两种情况下,sum(A[1..n])的和的最大值。


样例输入

6
6 10 -7 2 5 -12

样例输出

19
56
解释:
操作1取i=3,j=5;
操作2取i=2,j=6


提示

没有写明提示


题目来源

Dragonite提供翻译