You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

序列问题

题目描述

给定一个数组$a_1,a_2,...,a_n$，每次操作可以擦掉相邻的两个数，并写上这两个数中较大的那个，定义这一次操作的代价就是写上去的这个数。求只用这个操作将数组擦剩下一个数时，总代价的最小值。

输入格式

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

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

输出格式

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

样例 #1

样例输入 #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$。