题目内容

小塔有一个长度为$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