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

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

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

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

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

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

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

提示

数据范围

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