E. Merging Stones
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Walk Alone has $$$n$$$ piles of stones, and there are $$$a_i$$$ stones in the $$$i$$$-th pile.

He can do an operation to these stones for $$$n-1$$$ times. In each operation, he can select two piles of stones of size $$$x$$$ and $$$y$$$, and merge them (the two piles will become a larger pile of size $$$x+y$$$), and he will get $$$x\cdot y$$$ score after that.

Walk Alone wants to know the maximal total score he can get. Can you help him?

Input

The first line contains an integer $$$n\ (1\le n\le 10^5)$$$, the number of piles of stones.

The second line contains $$$n$$$ integers. The $$$i$$$-th integer $$$a_i\ (1\le a_i\le 10^4)$$$ indicates the number of stones in the $$$i$$$-th pile.

Output

Output an integer representing the maximal score Walk Alone can get.

Examples
Input
3
1 2 3
Output
11
Input
6
1 1 4 5 1 4
Output
98