Description

Arrange $n$ piles of stones around a circular playground. The goal is to merge them into a single pile in an orderly manner. The rule is that only two adjacent piles can be merged at a time, and the number of stones in the new pile is recorded as the score for that merge.

Write a program that reads the number of piles $n$ and the number of stones in each pile, and performs the following calculations:

1. Choose a merging strategy that maximizes the total score after $n-1$ merges.
2. Choose a merging strategy that minimizes the total score after $n-1$ merges.

Input Format

The first line of input contains an integer $n$, representing the number of piles of stones.

The second line contains $n$ integers, representing the number of stones in each pile.

Output Format

The output consists of two lines:

The first line contains the minimum total merge score,

The second line contains the maximum total merge score.

Sample 1

4
4 5 9 4

43
54

Data Range and Hint

For $100\%$ of the data, $1\le n \le 200$.