题目描述

对于一个给定的序列 $a _ 1, \cdots, a _ n$，我们对它进行一个操作 $\text{reduce}(i)$，该操作将数列中的元素 $a _ i$ 和 $a _ {i+1}$ 用一个元素 $\max(a _ i,a _ {i+1})$ 替代，这样得到一个比原来序列短的新序列。这一操作的代价是 $\max(a _ i,a _ {i+1})$。进行 $n-1$ 次该操作后，可以得到一个长度为 $1$ 的序列。

我们的任务是计算代价最小的 $\text{reduce}$ 操作步骤，将给定的序列变成长度为 $1$ 的序列。

输入格式

第一行为一个整数 $n$（$1 \leq n \leq 10 ^6$），表示给定序列的长度。

接下来的 $n$ 行，每行一个整数 $a _ i$（$0 \leq a _ i \leq 10 ^ 9$），为序列中的元素。

输出格式

只有一行，为一个整数，即将序列变成一个元素的最小代价。

3
1
2
3

5

提示

数据规模与约定

• 对于 $30\%$ 的测试数据，$n\le 500$；
• 对于 $50\%$ 的测试数据，$n \le 20000$；
• 对于 $100\%$ 的测试数据，$1 \le n \le 10^6$，$0 \le a_i \le 10^9$。