ADJDUCKS - Adjusting Ducks

no tags 

Wojtek's ducks' constant quacking annoys Tomek a great deal. When approached about the issue, Wojtek told Tomek to take it easy... Things got serious when Tomek bought a sling. They held a diplomatic meeting to reach a compromise. It turns out that when two or more ducks have the same quacking pitch, the sound becomes so constant, that they do not disturb Tomek at all. Fortunately enough, the local veterinarian can alter the pitches of ducks. For changing a duck's quacking pitch fromatob, he demands |b - a| zlotys. How many zlotys does Wojtek have to spend to make it so no duck is alone at its pitch?

Input

The first line of the input contains an integer n (2 ≤ n ≤ 105), the number of ducks. The second line contains n integers a1,...,an (1 ≤ ai ≤ 1018),the pitches of the ducks.

Output

Output the minimal cost of adjusting the ducks' pitches so that Tomek is no longer annoyed.

Example

Input:

5

42 1 3 3 6

Output:

38

Note

One possible solution is to adjust the pitch of the second duck to 3 (for a price of 2) and the pitch of the last duck to 42 (for a price of 36)


hide comments
rainy jain : 2016-05-18 01:48:37

@HNUE please provide some more test cases.


Added by:HNUE
Date:2014-10-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:HUST