Description

One day, Xuanxuan came up with a card game. The rules are as follows:

1. Initially, Xuanxuan has $n$ cards in hand, arranged in a row from left to right. Each card has an integer score value.
2. Then, each time, Xuanxuan may choose a consecutive segment of cards starting from the leftmost end of the sequence (at least $2$ cards) and replace them with one new card. The new card is inserted at the leftmost end of the sequence, and its score value equals the sum of the score values of the cards replaced in this operation.
3. Initially, Xuanxuan's total score is $0$. Each time a replacement operation is performed, the score value of the new card is added to the total score. The game ends when the sequence length becomes $1$, and Xuanxuan may also end the game at any moment.

Now you are given the score values of the cards in the sequence. Please help Xuanxuan compute the maximum total score he can obtain.

Input Format

The first line contains a positive integer $n$, representing the number of cards.

The next line contains $n$ integers separated by spaces. The $i$-th number $a_i$ represents the score value of the $i$-th card from left to right.

Output Format

Output a single integer on one line, representing the answer.

3
2 -1 2

4

7
-4 3 0 7 -3 -5 -3

9

Hint

Sample Explanation 1

The optimal strategy is to first choose the leftmost two cards, and the total score increases by $2 + (-1) = 1$. The two chosen cards are replaced by one card with score value $1$, and it is placed at the leftmost end of the sequence. Now the card values from left to right are $1$ and $2$.

Next, choose all cards in the current sequence, and the total score increases by $1 + 2 = 3$, making the total score $4$. The two chosen cards are replaced by one card with score value $3$, and it is placed at the leftmost end of the sequence. Now there is only one card with score value $3$, and the game ends.

Sample Explanation 2

The optimal strategy is to first choose the leftmost four cards, and the total score increases by $(-4) + 3 + 0 + 7 = 6$. The four chosen cards are replaced by one card with score value $6$, and it is placed at the leftmost end of the sequence. Now the card values from left to right are $6, -3, -5, -3$.

Then choose the leftmost two cards, and the total score increases by $6 + (-3) = 3$, making the total score $9$. The two chosen cards are replaced by one card with score value $3$, and it is placed at the leftmost end of the sequence. Now the card values from left to right are $3, -5, -3$.

At this point, no matter what operation is performed, the total score cannot be increased further, so Xuanxuan chooses to end the game.

Constraints and Notes

For test points $1 \sim 6$: $1 \le n \le 16$, $|a_i| \le 100$.

For test points $7 \sim 12$: $1 \le n \le 10^3$, $|a_i| \le 100$.

For test points $13 \sim 20$: $1 \le n \le 10^5$, $|a_i| \le 10^5$.

Translated by ChatGPT 5