## What is DP on Interval?

DP on interval is an extension of linear dynamic programming. When dividing the problem in stages, it has a lot to do with the order in which the elements appear in the stage and which elements from the previous stage are merged.

Features of interval DP:

Merger : that is to integrate two or more parts, of course, it can also be reversed;
Features : able to decompose the problem into a form that can be combined in pairs;

Solution : Set the optimal value for the entire problem, enumerate the merge points, decompose the problem into two parts, and finally merge the optimal values ​​of the two parts to get the optimal value of the original problem.

dp(i,j) = max(dp(i,j), dp(i,k) + dp(k+1,j) +cost)


## Interval DP Illustrated: Stone Merger

The piles of stones are discharged around the circular playground. Now the stones are to be combined into a pile in an orderly manner. It is stipulated that only two adjacent piles can be selected and merged into a new pile each time, and the number of stones in the new pile is recorded as the combined score.

Please write a program to read the heap count n and the number of stones in each pile, and calculate as follows:

Choose a scheme of merging stones (n-1 times) so that the sum of the combined scores is the largest. Choose a scheme of merging stones (n-1 times) so that the sum of sub-merged scores is the smallest.

Sample Input:

4
4 5 9 4


Sample Output:

43
54


### Solution

Since the question is a ring, we duplicate the array to make an array of size 2xn. Then we can just use normal linear array interval DP.