PEG Judge - SMAC 08/09 (Oct) #4

Sane's Monthly Algorithms Challenge: October 2008

Cow Daycare (Advanced Level)

Farmer John has just opened up a new daycare for cows of all sizes. The daycare consists of n (1 ≤ n ≤ 100, 000) cow pens. Each cow pen is built differently to accommodate cows of a unique size from 1 to n.

There is a mother cow inside every pen whose job is to take care of all the cows inside it. When there are no cows inside her pen, she does not need to do any work. For every new cow added to her pen, the amount of work she has to do to take care of each individual cow is increased by 1.

For example, if she has 1 cow she does 1 piece of work. If she has 2 cows she does 4 pieces of work. 3 cows is 9 pieces of work. So on and so forth.

The daycare had become so popular that Farmer John is taking in more cows than the mother cows can handle. To fix this, he realizes that he can lessen the number of cows in some pens (and thus the amount of work done by some mothers) by moving smaller cows to the pens built for larger cows.

Only smaller cows can be moved to larger pens (larger cows can not be moved to smaller pens). The size of each cow in a pen does not affect the amount of work done by a mother cow (only the quantity does). Moreover, there is no limit to the number of cows that can be moved inside a pen.

Given the number of cow pens and the number of cows of each size, move the cows around so that the total amount of work done by all of the mother cows is minimal.

Input

The first line of the input consists of a single integer, n (1 ≤ n ≤ 100,000), representing the number of uniquely sized cow pens.

The next n lines that follow will each contain a non-negative integer ≤ 100 on the i'th line, representing the number of cows that are size i. There will be one test case where cows rule the planet and each integer may be as large as 100,000.

Output

Output the sum of all work done by each mother such that it's minimal.
Note that it may be necessary to use a 64-bit integer (long long in C/C++, int64 in PAS) to compute your answer.

Sample Input

Sample Output

Explanation of Sample Data

Two of the size 1 cows are moved to pen 2 and another is moved to pen 3. The size 2 cow and one of the size 3 cows move to pen 4. The mothers in 2, 3, and 4 each do four pieces of work while the mother in pen 1 does 1 piece of work. 1 + 4 + 4 + 4 = 13. While there are other equally optimal placements, there exist none better than 13.

Before (Total Work = 21)
4x#1; 1x#2; 2x#3; 0x#4