Maximum Score with Two Diagonals

You are given N balls and N cups numbered from 1 to N from left to right. Initially, ball i is aligned with cup i, so if nothing happens, ball i falls into cup i. Each cup i has an associated score c_i (which can be negative). When a ball falls into a cup, you earn the cup's score. (Each cup can receive any number of balls.)

You are allowed to draw exactly one line of Type 1 and exactly one line of Type 2 under the following rules:

• Type 1 (\(\nearrow\searrow\)): Choose two distinct cups with indices \(i\) and \(j\) such that \(i < j\). Then all balls with indices from \(i\) to \(j\) are forced to fall into cup \(j\). In other words, ball \(k\) (for \(i \le k \le j\)) will yield a score of \(c_j\) instead of \(c_k\).
• Type 2 (\(\nwarrow\swarrow\)): Choose two distinct cups with indices \(i\) and \(j\) (with \(i < j\)). Then all balls with indices from \(i\) to \(j\) are forced to fall into cup \(i\). In other words, ball \(k\) (for \(i \le k \le j\)) will yield a score of \(c_i\) instead of \(c_k\).

The final score is the sum of scores obtained by all balls after applying the modifications. Formally, if the original score is \(S = \sum_{i=1}^{N} c_i\), then drawing a line changes the score for balls in the affected segment. For a Type 1 line defined by cups \(i\) and \(j\), the new score becomes:

[ S + \left[(j-i+1) \times c_j - \sum_{k=i}^{j} c_k\right]. ]

Similarly, for a Type 2 line defined by cups \(i\) and \(j\), the new score becomes:

[ S + \left[(j-i+1) \times c_i - \sum_{k=i}^{j} c_k\right]. ]

Your task is to choose exactly one Type 1 line and exactly one Type 2 line (independently) to maximize the final score in each case. Output two numbers: the maximum score obtainable by using a single Type 1 line and the maximum score obtainable by using a single Type 2 line.

Note: You must choose a pair of cups \((i,j)\) with \(i < j\) for each type even if the modification decreases the score.

inputFormat

The first line contains an integer N (\(2 \le N \le 10^5\)).

The second line contains N integers \(c_1, c_2, \dots, c_N\) (\(|c_i| \le 10^9\)) separated by spaces.

outputFormat

Output two integers separated by a space: the maximum final score obtained with exactly one Type 1 line and the maximum final score obtained with exactly one Type 2 line.

sample

5
1 -2 3 -4 5

25 10