Ada and Alley
As you might already know, Ada the Ladybug is a farmer. She has a long alley of trees. She wants the alley to look good so she has decided to make the heights of all trees equal. She has two possible operations: she can either cut the top of a tree, decreasing its height by one (at cost of 1) or cut the tree down (at cost of heighti).
Input
The first line of input will contain 1 ≤ N ≤ 3*105, the number of trees.
The next line will contain N integers 0 ≤ Hi ≤ 109
Output
Print the minimal cost to make the height of all trees in alley equal.
Example Input
5 1 2 3 4 5
Example Output
6
Example Input
3 1 4 2
Example Output
3
Example Input
4 1 6 1 1
Example Output
3
Example Input
6 7 11 13 1 3 5
Example Output
18
Example Input
7 1 11 4 13 5 10 7
Example Output
21