ADACUT - Ada and Alley

no tags 

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

hide comments
wisfaq: 2017-11-21 16:31:01

@julkas: Thanks

julkas: 2017-11-20 19:19:35

@wisfaq Cut - 0, 11, 11, 0, 0, 0.
Total cost - 7+0+2+1+3+5=18. It's best.
Hope it helps.

wisfaq: 2017-11-18 21:19:45

Can someone explain why:
6
7 11 13 1 3 5

gives 18?

Pranay: 2017-11-02 06:35:16

KOPC12A with modifications


Added by:Morass
Date:2017-10-29
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All