题解

题面描述

给定一个长度为 $n$ 的数组 $a=[a_1,a_2,\dots,a_n]$。可以任意交换数组中任意两个元素任意次（也可以不交换），使得可以自由调整顺序。然后定义一次“合井”操作：

• 选取相邻的两个数 $a_i$ 和 $a_{i+1}$，合并成一个数，该数等于 $\max\{a_i,a_{i+1}\}$，合并时花费代价也等于 $\max\{a_i,a_{i+1}\}$。
• 数组合并后顺序不变，但长度减少 $1$。

要求经过恰好 $n-1$ 次“合井”操作，使得最终数组只有一个数，问最少花费多少代价？

题目内容

小红拿到一个长度为 $n$ 的数组 ${a_1,a_2,...,a_n}$ ，下标从 $1$ 开始定义一次“合井”操作为：

选定任意的两个相邻的元素 $a_i$ 和 $a_{i+1}$ ，将它们合并成一个数，其余元素按照原有顺序从前到后依次拼接。这个数等于 $a_i$ 和 $a_{i+1}$ 的最大值，花费代价也是 $a_i$ 和 $a_{i+1}$ 的最大值，数组长度减少 $1$ 。

例如 $a=[1,2,3,4,5]$ ，小红可以选定 $a_2$ 和 $a_3$，合井成 $3$，数组变为 $[1,3,4,5]$，花费代价 $3$ 。

在执行上述的"合并"操作前，小红可以选择任意两个元素，将它们交换任意次(也可以不交换)。求解，执行恰好 $n-1$轮“合并“操作，使得将数组 $a$ 合并的只剩一个数，最少需要花费多少代价?

输入描述

第一行输入一个整数 $n(1≦n≦ 10^5)$，表示数组长度。

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1 ≦ a_i≦ 10^9)$ 代表数组元素。

输出描述

输出一个整数，表示最小花费。

样例1

输入

3
3 2 1

输出

5

说明

在这个样例中，有两种直接合并的方法：

先合并 $3,2$ ，花费 $max${$3,2$}$= 3$;再合并{$3,1$},花费 $max${$3,1$}$= 3$。总花费 $6$ 。

先合并 $2,1$，花费 $max${$2,1$}$=1$;再合并 {$3,2$},花费 $max${$3,2$}$= 3$。总花费 $5$ 。

样例2

输入

5
1 4 5 3 2

输出

14