题目描述

小 O 正在玩一款叫做“消消乐”的游戏。游戏开始前，他会得到一个长度为 $n$ 的整数数组 $a_1, a_2, \dots, a_n$。

在每一轮中，他可以选择当前数组中的任意一个元素并将其删除。删除该元素后，他将获得该元素左右两边元素之和的分数。需要注意的是，如果一个元素被删除后它的左边或右边没有元素，则对应位置视为 $0$ 分。游戏一直进行直到数组中没有任何元素为止。

现在，小 O 想知道通过合理安排删除顺序，他最多能获得多少分。请你帮助他计算出这个最大得分。

形式化地说：给定一个长度为 $n$ 的数组 $a$，每次操作可以选定一个下标 $i$（满足 $1\le i\le m$，其中 $m$ 为当前数组长度），将元素 $a_i$ 移除，并得到得分 $L + R$，其中 $L$ 是 $a_i$ 左边元素的值（如果左边没有元素则为 $0$），$R$ 是 $a_i$ 右边元素的值（如果右边没有元素则为 $0$）。求在所有可能的操作顺序下，总得分的最大值。

输入格式

第一行包含一个整数 $n$ —— 表示数组的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ —— 表示数组中的元素。

输出格式

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

样例输入 1

3
1 2 3

样例输出 1

7

样例输入 2

4
1 5 2 4

样例输出 2

21

说明

样例解释

• 样例 $1$ 解释： 初始数组为 $[1, 2, 3]$。一种最优操作顺序如下：

  1. 删除 $2$，获得 $1+3=4$ 分，数组变为 $[1, 3]$；
  2. 删除 $1$，获得 $0+3=3$ 分，数组变为 $[3]$；
  3. 删除 $3$，获得 $0+0=0$ 分，数组变为 $[]$。 总得分为 $4+3+0=7$。

• 样例 $2$ 解释： 给出一种次优操作顺序作为参考：

  • 先删除 $5$，得 $1+2=3$ 分，数组变为 $[1, 2, 4]$；再删除 $2$，得 $1+4=5$ 分，数组变为 $[1, 4]$；再删除 $1$，得 $0+4=4$ 分，数组变为 $[4]$；最后删除 $4$，得 $0+0=0$ 分，总得分为 $3+5+4+0=12$。

  • 存在更优方案：先删除 $2$，得 $1+4=5$ 分，数组变为 $[1, 5, 4]$；再删除 $5$，得 $1+4=5$ 分，数组变为 $[1, 4]$；再删除 $1$，得 $0+4=4$ 分，数组变为 $[4]$；最后删除 $4$，得 $0+0=0$ 分，总得分为 $5+5+4+0=14$。

  实际上最大得分为 $21$，请选手自行思考如何达到。

数据范围

对于 $100\%$ 的数据，保证：

• $1 \le n \le 100$；
• $1 \le a_i \le 10^4$；
• 保证所有的输入数值均为整数。