Card Game Score Maximization

At the beginning, there is a sequence of n cards arranged from left to right. Each card has an integer value. The game is played as follows:

1. You start with total score 0.
2. In each move, you choose a contiguous group of at least 2 cards from the left side of the sequence. Remove these cards and insert a new card at the beginning whose value is the sum of the removed cards. Add this sum to your total score.
3. You may stop the game at any time. The game also ends when only one card remains in the sequence.

Given the initial values of the cards, determine the maximum total score you can achieve.

It can be shown that the optimal strategy is to always merge the first two cards, because this maximizes the number of times the earlier (and potentially larger) numbers are included in the score. With this strategy, the total score is the sum of all prefix sums (starting from the first two cards up to all n cards).

Mathematically, if the cards are x₁, x₂, ..., x_n, then the maximum score is:

$$\text{Score} = \sum_{k=2}^{n} \left(\sum_{i=1}^{k} x_i\right). $$

inputFormat

The first line contains an integer n (n ≥ 1) — the number of cards.

The second line contains n integers, where the i-th integer represents the score on the i-th card from left to right.

outputFormat

Output a single integer — the maximum total score that can be achieved.

sample

2
1 2

3