【GESP26年6月7级T2】消消乐

题目描述

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

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

特别地，如果相邻元素不存在则该元素的值视为 0。

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

输入格式

第一行，一个正整数 N，表示数组长度。

第二行，N 个非负整数 a_i，表示数组 A 中的整数。

输出格式

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

样例

输入样例 1

6
1 6 3 2 9 1

输出样例 1

55

输入样例 2

5
3 1415 926 53 58

输出样例 2

5771

数据范围

对于 30% 的测试点，保证 N ≤ 10，a_i ≤ 100。

对于所有测试点，保证 N ≤ 100，a_i ≤ 10000。