Combining Riceballs

Alphonse has N delicious riceballs arranged in a row, each with various sizes. He wants to give the largest possible riceball to his best friend. To achieve this, he can perform the following operations any number of times (possibly zero):

• If two adjacent riceballs have equal sizes, he can combine them into a new riceball whose size is the sum of the two. (The new riceball occupies the positions of the two original riceballs.)
• If two riceballs with equal sizes have exactly one riceball between them (regardless of its size), he can combine all three riceballs into one new riceball whose size is the sum of the three. (The new riceball occupies the positions of the three original riceballs.)

Formally, if we denote the size of a riceball by a number, then:

Operation 1: If two consecutive riceballs have size x, they can be combined to form a riceball of size \( x+x = 2x \).

Operation 2: If two riceballs of size x have exactly one riceball between them (of any size), they can be combined to form a riceball of size \( x + y + x = 2x+y \) (where y is the size of the middle riceball). Note that when the riceballs are combined by previous operations, the same rules apply.

After performing any sequence of operations, determine the maximum size of a riceball that Alphonse can obtain.

inputFormat

The first line contains a single integer N (the number of riceballs).

The second line contains N space-separated positive integers indicating the sizes of the riceballs in order.

outputFormat

Output a single integer representing the maximum size of any riceball that can be formed.

sample

7
47 12 12 3 9 9 3

48