808. Minimum Operations to Make Collection Unique

0

Medium

Faraz dislikes having duplicate numbers in a collection of integer numbers. On his 21st birthday, Mayank wants to gift him such a collection, but he is unaware of Faraz's preferences. Dhruv reminds Mayank about Faraz's aversion to duplicates. Now, both Mayank and Dhruv are trying to make all the numbers in the collection unique by performing a single operation multiple times. * In one operation, any number can be incremented by 1. Assist Dhruv and Mayank in determining the minimum number of operations required to make all the numbers in the collection unique.

Input Format

The first line contains an integer N, representing the total number of numbers in Mayank's collection.
The second line contains N integers, describing all the integer numbers in the collection.

Output Format

Print the minimum number of operations required to make all the numbers in the collection unique.

Example

Input

6 3 2 1 2 1 7

Output

6

Constraints

1 <= total integer numbers <= 10^5
0 <= Each integer Number <= 10^5