Description

Along the circumference of a circular track, there are $N$ piles of stones. We want to merge the stones into one pile in some order. Each time, we can only choose two adjacent piles and merge them into a new pile; the number of stones in the new pile is recorded as the score for that merge.

Design an algorithm to compute the minimal total score and the maximal total score for merging $N$ piles into $1$ pile.

Input Format

The first line contains the positive integer $N$, the number of piles.

The second line contains $N$ integers; the $i$-th integer $a_i$ denotes the number of stones in the $i$-th pile.

Output Format

Output a total of $2$ lines. The first line is the minimal total score, and the second line is the maximal total score.

4
4 5 9 4

43
54

Hint

Constraints: $1 \leq N \leq 100$, $0 \leq a_i \leq 20$.

Translated by ChatGPT 5