Description

给定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])的和的最大值。

Format

Input

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

Output

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

Samples

6
6 10 -7 2 5 -12

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