We’re preparing your current view and syncing the latest data.
You are given an array of integers. In one operation, you can decrement the value of any element by 1. The goal is to determine the minimum number of operations required to ensure all elements in the array have unique values (i.e., no two elements are equal). Output the minimum total number of decrements needed to achieve this.
The first line contains a single integer n (1 ≤ n ≤ 2×10^5) — the length of the array. The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 10^9) — the elements of the array.
Output a single integer — the minimum total number of operations required to make all elements of the array unique by decrementing only.
1 ≤ n ≤ 2×10^5, 1 ≤ ai ≤ 10^9
Example 1
Input
5 2 2 2 1 1
Output
3
Explanation
One way to achieve uniqueness is to think about making the array elements [2, 1, 0, 1, 1]. But 1 is repeated. Instead, by carefully decrementing, we can transform the array to [2, 1, 0, 1, 0], still duplicates. The optimal solution decrements elements to get [2, 1, 0, 1, 0] counting a total of 3 decrements.