410195: GYM103973 E Merging Stones

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?

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 an integer representing the maximal score Walk Alone can get.

3
1 2 3

11

6
1 1 4 5 1 4

98