Minimum Increments to Make Array Unique

You are given an array of integers. Your task is to modify the array so that each element is unique with the minimum number of increments. For every element (a_i) that is not strictly greater than the previous element (a_{i-1}), you must increment it until (a_i > a_{i-1}). Formally, after sorting the array, for every index (i) (with (1 \leq i < n)), if (a_i \leq a_{i-1}) then you must add (\Delta = a_{i-1} - a_i + 1) to (a_i). The goal is to minimize the total number of increments (\sum\Delta).

inputFormat

The first line of input contains a single integer (n) denoting the number of elements in the array. The second line contains (n) space-separated integers representing the elements of the array.

outputFormat

Output a single integer representing the minimum number of increments required to make every element in the array unique.## sample

3
1 2 2

1