消消乐

题目描述

给定⼀个由 个整数构成的数组 。每次你可以对数组 进⾏以下操作，直到数组 变为空： 指定 中的⼀个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 中删去。 特别地，如果相邻元素不存在则该元素的值视为 。例如，对于 可以进⾏以下操作： 指定元素 ，获得分数 ，删去 后 ； 指定元素 ，获得分数 ，删去 后 ； 指定元素 ，获得分数 ，删去 后 变为空。 请问你能获得的分数总和最⼤是多少？

输入格式

第⼀⾏，⼀个正整数 ，表⽰数组长度。 第⼆⾏， 个⾮负整数 ，表⽰数组 中的整数。

输出格式

输出⼀⾏，⼀个整数，表⽰能获得的最⼤分数总和。

样例输入 #1

6
1 6 3 2 9 1

样例输出 #1

55

样例输入 #2

5
3 1415 926 53 58

样例输出 #2

5771

数据范围

对于 的测试点，保证 ， 。 对于所有测试点，保证 ， 。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐⭐⭐ 。

测试点分布

生测试数据后，按实际 subtask 分组改写上表。