Stone Merging on a Circular Playground

You are given N piles of stones placed around a circular playground. You need to merge these piles into a single pile by repeatedly merging two adjacent piles. In every merge operation, you can only merge two adjacent piles (note that in a circle, the first and the last piles are adjacent). The cost (score) of a merge is equal to the sum of the number of stones in the two piles that are merged. Your task is to compute both the minimum total score and the maximum total score that can be achieved by merging all the piles into one pile.

The merging cost for merging piles from the i-th pile to the j-th pile can be computed using the following recurrence in LaTeX format:

[ \text{dp}[i][j] = \begin{cases} 0, & \text{if } i = j, \ \min_{i \le k < j}{\text{dp}[i][k] + \text{dp}[k+1][j]} + S(i,j), & \text{for minimum cost}, \ \max_{i \le k < j}{\text{dp}[i][k] + \text{dp}[k+1][j]} + S(i,j), & \text{for maximum cost}, \end{cases} ]

where the function S(i, j) denotes the sum of stones from the i-th to the j-th pile. Due to the circular arrangement, you may consider duplicating the sequence of piles and then applying a sliding window of length N to consider all possible break points.

inputFormat

The first line contains an integer N (the number of piles).

The second line contains N space-separated positive integers representing the number of stones in each pile, in clockwise order.

outputFormat

Output two integers separated by a space. The first integer is the minimum total score and the second integer is the maximum total score required to merge all the piles into one.

sample

3
1 2 3

9 11