410195: GYM103973 E Merging Stones
Description
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?
InputThe 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.
OutputOutput an integer representing the maximal score Walk Alone can get.
ExamplesInput3 1 2 3Output
11Input
6 1 1 4 5 1 4Output
98