ADACUT  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 height_{i}).
Input
The first line of input will contain 1 ≤ N ≤ 3*10^{5}, the number of trees.
The next line will contain N integers 0 ≤ H_{i} ≤ 10^{9}
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
hide comments
krunner:
20180513 15:36:12
Quite interesting problem, never met with this before, only 47 lines in Java :) 

iampijush:
20171214 16:17:46
I am getting correct answer on every given tc and also on generated random tcs from spoj toolkit. still, it says wrong answer. any clue ? Last edit: 20171214 16:18:24 

wisfaq:
20171121 16:31:01
@julkas: Thanks 

julkas:
20171120 19:19:35
@wisfaq Cut  0, 11, 11, 0, 0, 0.


wisfaq:
20171118 21:19:45
Can someone explain why:


Pranay:
20171102 06:35:16
KOPC12A with modifications 
Added by:  Morass 
Date:  20171029 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 