P17015 [GESP202606 Level 7] Elimination Game

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?

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 one line containing one integer, representing the maximum total score you can obtain.

### 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