题目描述

薯条哥拿到一个长度为 $n$ 的数组 $\left \{ a_1,a_2,...,a_n \right \}$ ，下标从 $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\le n\le 10^5)$，表示数组长度。

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

输出描述

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

样例1

输入

3
3 2 1

输出

5

样例解释

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

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

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

样例2

输入

5
1 4 5 3 2

输出

14