给定一个由 n 个整数构成的数组 a=[a_1,\ldots,a_n]。每次你可以对数组 a 进行以下操作，直到数组 a 变为空：

指定 a 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 a 中删去。特别地，如果相邻元素不存在则该元素的值视为 0。

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

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

第二行，n 个非负整数 a_1,\ldots,a_n，表示数组 a 中的整数。

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

数据范围

对于 40% 的测试点，保证 1 \le n \le 50，0 \le a_i \le 10^3。

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

GESP七级26年6月