题目描述

给你一个长度为 $n$ 的序列，你每次可以将一个序列分割成两个连续的的子序列， 分割的代价为原序列的总和。 现在允许你在初始时将序列重新排列一次。 问分割成 $n$ 个长度为 $1$ 的序列的最大总代价是多少？

输入描述

第一行一个数 $n$ 表示原序列的长度。 接下来一行 $n$个数 $a_i$ 表示原序列的第i个数。 $2<=n<=100000$ $0<=a_i<=10000$

输出描述

一行一个整数表示答案。

输入样例

4
3 2 4 1

输出样例

26

说明

$[3,2,4,1]$ 重排 $->[1,2,3,4]$-> $[1],[2,3,4]$ -> $[1],[2],[3,4]$ -> $[1],[2],[3],[4]$。