Our magician Harry decided to give a stage performance. To perform his famous magic trick, he needs to stick his hand inside the hat and take two rabbits out, magically turn them into one rabbit and then put it back inside the hat. He continues to do this until he is left with only one rabbit. Every transformation that Harry does uses up his energy, the bigger the rabbits are, the more energy Harry needs to use in order to perform his magic trick. Given the number of the rabbits inside the hat and their sizes, help Harry to successfully perform the trick while saving his energy for the rest of the show.
When joining two rabbits together, the sum of their sizes will represent the amount of energy needed for that specific transformation, that number will also be the size of the new rabbit.
The first line contains an integer \(n(1\leq n \leq 10^5)\), the second line contains the array of \(n\) rabbits \(x_1, x_2,...,x_n(-10^4 \leq x_i \leq 10^4)\) where the values represent their size.
An integer - the smallest amount of total energy that Harry will need to use to perform his trick.
Sample Input 1
4 3 7 2 9
Sample Output 1
Sample Input 2
5 5 1 4 8 2
Sample Output 2