消消乐

题目描述

给定一个由 $n$ 个整数构成的数组 $a$。每次你可以对数组 $a$ 进行以下操作，直到数组 $a$ 变为空：

指定 $a$ 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 $a$ 中删去。

特别地，如果相邻元素不存在则该元素的值视为 0。例如，对于 $a = [1, 6, 3]$ 可以进行以下操作：

• 指定元素 6，获得分数 $1 + 3 = 4$，删去 6 后 $a$ 变为 $[1, 3]$；
• 指定元素 1，获得分数 $0 + 3 = 3$，删去 1 后 $a$ 变为 $[3]$；
• 指定元素 3，获得分数 $0 + 0 = 0$，删去 3 后 $a$ 变为空。

请问你能获得的分数总和最大是多少？

输入格式

• 第一行，一个正整数 $n$，表示数组长度；
• 第二行，$n$ 个非负整数 $a_i$，表示数组 $a$ 中的整数。

输出格式

输出一行，一个整数，表示能获得的最大分数总和。

数据范围

对于所有测试点，保证 $1 \le n \le 100$，$0 \le a_i \le 10^6$。

样例

输入样例 1

6
1 6 3 2 9 1

输出样例 1

55

输入样例 2

5
1 2 3 4 5

输出样例 2

26