Xuanxuan thought of a card game one day, and the rules are as follows:

1. Initially, Xuanxuan has $n$ cards arranged in a row from left to right, each with an integer score.
2. In each step, Xuanxuan can choose a contiguous sequence of cards starting from the leftmost card (at least $2$ cards) and replace them with a new card. The new card is inserted at the leftmost end of the sequence, and its score is the sum of the scores of the cards replaced in this operation.
3. Initially, Xuanxuan's total score is $0$. Each time a card replacement operation is performed, the score of the new card is added to the total score. The game ends when the sequence length is $1$, or Xuanxuan can choose to end the game at any time.

Given the scores of the cards in the sequence, please help Xuanxuan calculate the maximum total score he can obtain.

Input

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

The next line contains $n$ space-separated integers, where the $i$-th number $a_i$ represents the score of the $i$-th card from left to right.

Output

A single line containing an integer representing the answer.

Examples

Input 1

3
2 -1 2

Output 1

4

Note 1

The optimal strategy is to first choose the two leftmost cards; the total score increases by $2 + (-1) = 1$. The two cards are replaced by a new card with a score of $1$, which is placed at the leftmost end of the sequence. The scores of the cards from left to right are now $1$ and $2$.

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

Input 2

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

Output 2

9

Note 2

The optimal strategy is to first choose the four leftmost cards; the total score increases by $(-4) + 3 + 0 + 7 = 6$. The four cards are replaced by a new card with a score of $6$, which is placed at the leftmost end of the sequence. The scores of the cards from left to right are now $6, -3, -5, -3$.

Then, choose the two leftmost cards; the total score increases by $6 + (-3) = 3$, making the total score $9$. The two cards are replaced by a new card with a score of $3$, which is placed at the leftmost end of the sequence. The scores of the cards from left to right are now $3, -5, -3$.

At this point, no further operations can increase the total score, so Xuanxuan chooses to end the game.

Subtasks

Test cases $1\sim6$ satisfy: $1\le n\le 16, |a_i| \le 100$.

Test cases $7\sim 12$ satisfy: $1\le n\le 10^3, |a_i| \le 100$.

Test cases $13\sim 20$ satisfy: $1\le n\le 10^5, |a_i| \le 10^5$.