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 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

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

hide comments
2019-03-20 10:09:54
Basic problem. Just sort and try to develop the series. All trees on right should be cut and all trees on left should be removed! AC in one go :)
2018-12-19 03:11:16
@adhya: if you cut down the trees with heights 1,3,5,7 (this will cost you 1+3+5+7 = 16) and then shorten the 13 tree by two (costing 2), all remaining trees are now height 11, and it cost you 18 total.
2018-09-21 13:53:58
For following test case:
6
7 11 13 1 3 5

I can't understand why it is 18.
2018-05-13 15:36:12
Quite interesting problem, never met with this before, only 47 lines in Java :)
2017-12-14 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: 2017-12-14 16:18:24
2017-11-21 16:31:01 wisfaq
@julkas: Thanks
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.
2017-11-18 21:19:45 wisfaq
Can someone explain why:
6
7 11 13 1 3 5

gives 18?
2017-11-02 06:35:16 Pranay
KOPC12A with modifications
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.