Problem Description

You are given an array $a = [a_1, \ldots, a_n]$ consisting of $n$ integers. Each time, you may perform the following operation on the array $a$ until $a$ becomes empty:

• Choose an element in $a$, gain a score equal to the sum of its adjacent elements on both sides, and then delete this element from $a$.

In particular, if an adjacent element does not exist, its value is considered to be $0$. For example, for $a = [1, 2, 3]$, you can do the following operations:

• Choose element $2$, gain a score of $1 + 3$, after deleting $2$ we have $a = [1, 3]$;
• Choose element $1$, gain a score of $0 + 3$, after deleting $1$ we have $a = [3]$;
• Choose element $3$, gain a score of $0 + 0$, after deleting $3$ the array $a$ becomes empty.

What is the maximum possible total score you can obtain?

Input Format

The first line contains a positive integer $n$, representing the length of the array.

The second line contains $n$ non-negative integers $a_1, \ldots, a_n$, representing the integers in the array $a$.

Output Format

Output one line containing one integer, representing the maximum total score you can obtain.

6
1 6 3 2 9 1

55

5
3 1415 926 53 58

5771

Hint

Constraints

For $40\%$ of the testdata, it is guaranteed that $1 \le n \le 50$ and $0 \le a_i \le 10^3$.

For all testdata, it is guaranteed that $1 \le n \le 100$ and $0 \le a_i \le 10^9$.

Translated by ChatGPT 5