Problem Description

Translated from CCC2016 Senior T4 “Combining Riceballs”

Alphonse has $N$ delicious riceballs of different sizes, arranged in a line. He wants to give the largest riceball to his best friend. He can perform the following operations:

• If two adjacent riceballs have the same size, Alphonse can combine them into one new riceball. The new riceball’s size is the sum of the two original riceballs’ sizes. It will occupy the positions previously occupied by the two original riceballs.

• If two riceballs have the same size, and there is exactly one riceball between them, Alphonse can also combine them into one new riceball. (There is no restriction on the middle riceball’s size.) The new riceball’s size is the sum of the three original riceballs’ sizes, and it occupies the positions previously occupied by the three original riceballs.

Alphonse may perform the operations any number of times, in any order.

After performing $0$ or more operations, determine which riceball he should give to his friend.

Input Format

The first line contains an integer $N$ $(1 \le N \le 400)$.

The second line contains $N$ space-separated integers, giving the sizes of the riceballs from left to right. Each integer is at most $1\ 000\ 000$.

Output Format

Output the maximum riceball size that Alphonse can obtain.

7
47 12 12 3 9 9 3

48

4
1 2 3 1

3

Hint

Sample Explanation 1.

One possible sequence of merges is: combine the two riceballs of size $12$ to get a riceball of size $24$. Then combine the two riceballs of size $9$ to get a riceball of size $18$. Next, combine the three riceballs of size $3, 18,$ and $3$ to get a riceball of size $24$. Finally, combine the two riceballs of size $24$ to get a riceball of size $48$.

Sample Explanation 2.

We cannot perform any operation, so the answer is $3$.

For $\frac1{15}$ of the testdata, $N = 4$.

For another $\frac2{15}$ of the testdata, $N \le 10$.

For another $\frac5{15}$ of the testdata, $N \le 50$.

Translated by ChatGPT 5