思路

题目要求枚举左右端点，求解出所有的区间和，这使得每个位置在区间中的贡献不同。例如，在样例$1$中，所有的子区间为 $[1,1], [1,2], [1,3], [2,2], [2,3], [3,3]$。其中，位置$1$贡献$2$次，位置$2$贡献$4$次，位置$3$贡献$2$次。题目要求最小化子区间和，因此需要让较大的数贡献较少的次数。将较大的数放在贡献次数少的位置，比如将$2$和$3$放在位置$1$和$3$，数字$1$放在贡献次数较多的位置$2$。最终数组排列结果为$[2,1,3]$或$[3,1,2]$，最小值为$19$。

对于每个位置，统计其贡献次数，然后通过排序将数值大的数放置在贡献次数少的位置。对于位置$i$，包含$i$的区间$[l, r]$满足$l \leq i \leq r$，因此有$0 \leq l \leq i, i \leq r < n$。位置$i$的贡献次数$nums[i]$为$(i+1) \times (n-i)$。最小的贡献即为排序后的每个数乘以对应的贡献次数：

题目内容

小红有一个长度为$n$的数组$a$，他定义了一个函数$f:f(l,r)=\sum^r_{k=l}a_k$，即$f$($l,r$)表示数组$a$在[$l,r$]这一段区间的区间和。

现在小红有一个重新任意排列数组$a$的机会，他想要最小化$\sum^n_{l=1}\sum^n_{r=l}f(l,r)$，即最小化所有区间对于f的值之和，请你帮他算算最小的这个值吧。

输入描述

第一行输入一个正整数$n$($1≤n≤2×10^5$)代表数组中元素的个数。

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

输出描述

在一行上输出一个整数，表示题中所求答案。

样例1

输入

3 
1 2 3

输出

19

说明

重新排列为{$1,2,3$},此时全部区间为[$2$]、[$1$]、[$3$]、[$2,1$]、[$1,3$]和[$2,1,3$]总和恰好为$19$，可以证明这是最小的。

样例2

输入

6
1 1 4 5 1 4

输出

128