[BOI2007] Sequence 序列问题
题目描述
对于一个给定的序列 $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$),为序列中的元素。
输出格式
只有一行,为一个整数,即将序列变成一个元素的最小代价。
输入输出样例
输入样例 #1
3
1
2
3
输出样例 #1
5
说明
### 数据规模与约定
- 对于 $30\%$ 的测试数据,$n\le 500$;
- 对于 $50\%$ 的测试数据,$n \le 20000$;
- 对于 $100\%$ 的测试数据,$1 \le n \le 10^6$,$0 \le a_i \le 10^9$。