给定一个序列 $a_1, \dots, a_n$。我们可以使用操作 $reduce(i)$ 来操作该序列，该操作将元素 $a_i$ 和 $a_{i+1}$ 替换为单个元素 $max(a_i, a_{i+1})$，从而得到一个更短的新序列。该操作的代价为 $max(a_i, a_{i+1})$。经过 $n - 1$ 次 $reduce$ 操作后，我们得到一个长度为 1 的序列。我们的任务是计算最优合并方案的代价，即能够将序列缩减为长度为 1 且总代价最小的 $reduce$ 操作序列的代价。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 1,000,000$)，表示序列的长度。

接下来的 $n$ 行，每行包含一个整数 $a_i$ ($0 \le a_i \le 1,000,000,000$)，表示序列的元素。

输出格式

输出的第一行也是唯一一行，输出将序列缩减为单个元素的最小总代价。

样例

输入样例 1

3
1
2
3

输出样例 1

5

数据范围

• 对于 $30\%$ 的测试数据，满足 $n \le 500$。
• 对于 $50\%$ 的测试数据，满足 $n \le 20,000$。