Minimum Increment to Make Array Unique

Given an array \(A\) of non-negative integers, your task is to make all elements unique by incrementing some of them. You can increase an element by 1 at a cost of 1 unit per increment. Formally, if you increment an element \(A_i\) by \(k\), the cost is \(k\) and the new value becomes \(A_i + k\). Determine the minimum total cost required to make every element in the array unique.

Input Example: For an input array [1, 2, 2], you can change it to [1, 2, 3] with a total cost of 1.

inputFormat

The input is provided via standard input (stdin). The first line contains an integer \(n\), representing the number of elements in the array. The second line contains \(n\) space-separated non-negative integers representing the array \(A\).

Example:

3
1 2 2

outputFormat

The output is a single integer printed to standard output (stdout), which is the minimum total cost required to make all elements in the array unique.

Example:

1

3
1 2 2

1