Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.
Return the least number of moves to make every value in A unique.
 
Example 1:
Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].


Example 2:
Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

 

Note:

0 <= A.length <= 40000
0 <= A[i] < 40000

Difficulty: interview

Starter code:

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        

Solutions:
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        
        A.sort()
        prev = A[0]
        res = 0
        for num in A[1:]:
            if num <= prev:
                prev += 1
                res += prev-num

            else:
                prev = num
        
        return res


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0

        n = len(A)
        A.sort()

        tail_num = A[0]
        result = 0
        for i in range(1, n):
            if A[i] > tail_num:
                tail_num = A[i]
            else:
                tail_num += 1

            # result = result + (tail_num - A[i])
            result += tail_num - A[i]

        return result


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # Need to have a count
        # Sort the array.
        result = 0
        A.sort()
        
        # Start from position 1 and traverse to end. 
        for i in range(1, len(A)):
            # Check previous value >= current value 
            # If so, increment A[i] by A[i-1] + 1
            if (A[i-1] >= A[i]):
                result += A[i-1] - A[i] + 1
                A[i] = A[i-1] + 1
        
        # Return count
        return result

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(60000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A: return 0
        min_num = min(A)
        max_num = max(A)
        count = collections.Counter(A)
        taken = []
        
        ans = 0
        for x in range(100000):
            if x> max_num and (not taken): break
            if count[x] >= 2:
                # taken.extend([x] * (count[x] - 1))
                taken = taken + [x] * (count[x] - 1)
            elif taken and count[x] == 0:
                ans += x - taken.pop()
                
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        
        taken = []
        
        mv = 0
        
        for i in range(80000):
            if count[i] > 1:
                taken.extend([i] * (count[i] - 1))
            elif taken and count[i] == 0:
                mv += (i - taken.pop())
        return mv

import collections
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counter = collections.Counter(A)
        res = 0
        for i in range(80000):
            if counter[i] > 1:
                res += counter[i] - 1
                counter[i+1] += counter[i] - 1
        return res

from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        hm = dict(Counter(A))
        stack = [k for k, v in list(hm.items()) if v > 1]
        ans = 0
        while stack:
            k = stack.pop()
            hm[k + 1] = hm.get(k + 1, 0) + hm[k] - 1
            ans += hm[k] - 1            
            hm[k] = 1
            if hm[k + 1] > 1:
                stack.append(k + 1)
                
        return ans
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A: return 0
        min_num = min(A)
        max_num = max(A)
        count = collections.Counter(A)
        taken = []
        
        ans = 0
        for x in range(100000):
            if x > max_num and (not taken): break
            if count[x] >= 2:
                # taken.extend([x] * (count[x] - 1))
                taken = taken + [x] * (count[x] - 1)
            elif taken and count[x] == 0:
                ans += x - taken.pop()
                
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(80001):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans
        


class Solution:
    def minIncrementForUnique(self, A):
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(80000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        N, ans = 40000, 0
        freq, free_slot = [0]*N, 0
        for n in A:
            freq[n] += 1
        for i, r in enumerate(freq):
            if r:
                ans += (r*(r-1))//2 + (free_slot - i)*r
                free_slot += r
            else:
                free_slot = max(free_slot, i+1)
        return ans
                
            
            


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count=collections.Counter(A)
        used=[]
        ans=0
        for x in range(90001):
            if count[x] >= 2:
                used.extend([x] * (count[x]-1))
            elif used and count[x]==0:
                ans+=x-used.pop()
        return ans

#         count = collections.Counter(A)
#         taken = []

#         ans = 0
#         for x in range(100000):
#             if count[x] >= 2:
#                 taken.extend([x] * (count[x] - 1))
#             elif taken and count[x] == 0:
#                 ans += x - taken.pop()
#         return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        n = len(A)
        A.sort()
        stack = []
        ans = 0
        A.append(A[-1] + n)
        for i in range(1, n+1):
            if A[i] == A[i-1]:
                stack.append(A[i])
            else:
                for r in range(1, A[i] - A[i-1]):
                    if stack:
                        ans += A[i-1] + r - stack.pop()
                    else:
                        break            
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        ans = 0
        waiting = 0
        for x in range(80000):
            if count[x]>=2:
                # waiting.extend([x]*(count[x]-1))
                waiting += count[x]-1;
                ans -= x * (count[x]-1);
            elif waiting>0 and count[x]==0:
                # ans += x - waiting.pop()
                waiting-=1;
                ans+=x;
        return ans


class Solution(object):
    def minIncrementForUnique(self, A):
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans

class Solution(object):
    def minIncrementForUnique(self, A):
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        seen = []
        
        res = 0
        for x in range(100000):
            if count[x] >= 2:
                seen.extend([x] * (count[x] - 1))
            elif seen and count[x] == 0:
                res += x - seen.pop()
        
        return res

from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counts = Counter(A)
        taken = []
        ans = 0
        
        for num in range(90001):
            num_count = counts[num]
            if num_count >= 2:
                taken.extend([num] * (num_count - 1))
            elif taken and num_count == 0:
                ans += num - taken.pop()
                
        return ans


# https://leetcode.com/problems/minimum-increment-to-make-array-unique/

from typing import List
from collections import Counter


class Solution:
    def minIncrementForUnique_bruteforce(self, A: List[int]) -> int:
        counts = Counter(A)
        tot_count = 0

        for n in A:
            while counts[n] > 1:
                counts[n] -= 1
                n += 1
                counts[n] += 1
                tot_count += 1

        return tot_count

    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        counts = Counter(A)

        count = 0

        taken = []

        for i in range(100000):
            if counts[i] >= 2:
                taken.extend([i for _ in range(counts[i] - 1)])

            elif taken and counts[i] == 0:
                count += i - taken.pop()

        return count


class Solution(object):
    def minIncrementForUnique(self, A):
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans
    
    


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        result = 0

        for i in range(1, len(A)):
            if A[i] > A[i-1]:
                continue
            result += A[i-1]-A[i]+1
            A[i] = A[i-1]+1

        return result


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        f = 80001 * [0]
        
        max_ = -1
        
        for i in A:
            f[i] += 1
            max_ = max(max_, i)
        
        hold = []
        
        res = 0
        
        for i in range(max_ + len(A) + 1):
            if hold and f[i] == 0:
                res += i - hold.pop()
                
            elif f[i] > 1:
                hold = (f[i] - 1) * [i] + hold
                
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        f = 80001 * [0]
        
        max_ = -1
        
        for i in A:
            f[i] += 1
            max_ = max(max_, i)
        
        hold = []
        
        res = 0
        
        for i in range(max_ + len(A) + 1):
            if f[i] == 0 and hold:
                res += i - hold.pop()
                
            elif f[i] > 1:
                hold = (f[i] - 1) * [i] + hold
                
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # [1, 2, 2, 2, 4, 4, 5]
        #     ^
        # [1, 2, 2, 2, 4, 4, 5]
        #        ^
        # [1, 2, 3, 4, 5, 6, 7] = 8
        
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            # print(taken)
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []

        ans = 0 

        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))

            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count=collections.Counter(A)
        #print(count)
        taken=[]
        ans=0
        for x in range(100000):
            if count[x]>=2:
                taken.extend([x]*(count[x]-1))
            elif taken and count[x]==0:
                ans+=x-taken.pop()
        return ans

from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        cnt, ans = Counter(A), 0
        
        for i in range(100000):
            if cnt[i] > 1:
                ans += cnt[i] - 1
                cnt[i + 1] += cnt[i] - 1
                
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counter = collections.Counter(A)
        taken = []
        result = 0
        
        for i in range(100000):
            if counter[i] > 1:
                taken.extend([i]*(counter[i]-1))
            elif taken and counter[i] == 0:
                result += (i-taken.pop())
        return result

from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # Counting
        # If there are 2 or more values x in A, save the extra duplicated values to increment later.
        # If there are 0 values x in A, then a saved value v gets incremented to x.
        count = Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()

        return ans



class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        
        taken = []
        
        ans = 0
        
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x]*(count[x] - 1))
            elif taken and count[x] == 0 :
                ans += x - taken.pop()
        return ans
                
        
        


from collections import Counter
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        c=Counter(A)
        prev=-1
        ans=0
        for key in sorted(c):
            if key<=prev:
                ans+=(0+c[key]-1)*c[key]//2+c[key]*(prev-key+1)
                prev=key+c[key]-1+prev-key+1
            else:
                ans+=(0+c[key]-1)*c[key]//2
                prev=key+c[key]-1
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []
        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        taken =[]
        
        count = collections.Counter(A)
        moves = 0
        for i in range(100000):
            if count[i]>=2:
                taken.extend([i]*(count[i]-1))
            elif taken and count[i]==0:
                moves+=i-taken.pop()
        return moves


class Solution(object):
    def minIncrementForUnique(self, A):
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans
            
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []
        
        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x]-1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
                
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counts = Counter(A)
        increments = 0

        # upper bound of the problem
        for num in range(100000):
            count = counts[num]
            if count > 1:
                increments += count - 1
                counts[num] = 1
                if not counts[num + 1]:
                    counts[num + 1] = 0
                counts[num + 1] += count - 1
        
        return increments

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        
        count = collections.Counter(A)
        taken = []

        ans = 0
        for x in range(100000):
            if count[x] >= 2:
                taken.extend([x] * (count[x] - 1))
            elif taken and count[x] == 0:
                ans += x - taken.pop()
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        c = collections.Counter(A)
        mv = 0
        need = 0
        for i in sorted(c):
            
            mv += max(need - i, 0) * c[i] + c[i] * (c[i] - 1) // 2
            need = max(need, i) + c[i]
        return mv

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # if len(A) < 2:
        #     return 0
        # index = []
        # count = 0
        # init = A[0]
        # for a in A:
        #     if a not in index:
        #         index.append(a)
        #     else:
        #         while a in index:
        #             count+=1
        #             a += 1
        #         index.append(a)
        # return count
        A.sort()
        ans = 0
        for i in range(1,len(A)):
            if A[i-1] >= A[i]:
                ans += A[i-1] - A[i] + 1
                A[i] += A[i-1] - A[i] + 1
                
        return ans

from collections import Counter
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        c=Counter(A)
        ans=0
        prev=-1
        for num in sorted(c):
            ans+=max(0,(prev-num+1))*c[num]+(c[num]-1)*c[num]//2
            prev=num+max(0,(prev-num+1))+(c[num]-1)
            
        return ans
                


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        a = sorted(A)
        
        res = 0
        
        for i in range(0, len(a)-1):
            if a[i+1] == a[i]:
                a[i+1] += 1
                res += 1
            elif a[i+1] < a[i]:
                k = a[i] - a[i+1] + 1
                a[i+1] += k
                res += k

        return res

class Solution:
    def minIncrementForUnique(self, A):
        bar = -1
        res = 0
        for a in sorted(A):
            if a < bar:
                res += bar - a
            bar = max(bar + 1, a + 1)
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:        
        # Solution 1
        A.sort()
        A.append(100000)
        result = taken = 0
        
        for i in range(1, len(A)):
            if A[i-1] == A[i]:
                taken += 1
                result -= A[i]
            else:
                give = min(taken, A[i]-A[i-1]-1)
                result += give*(give+1)//2 + give*A[i-1]
                taken -= give
        return result
        
        # Solution 2
        counter = collections.Counter(A)
        taken = []
        result = 0
        
        for i in range(100000):
            if counter[i] > 1:
                taken.extend([i]*(counter[i]-1))
            elif taken and counter[i] == 0:
                result += (i-taken.pop())
        return result

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        #18:31
        if not A:
            return 0
        A.sort()
        next_available = A[0]
        res = 0
        for a in A:
            if a >= next_available:
                next_available = a + 1
            else:
                res += next_available - a
                next_available += 1
        return res
            


class Solution:
    def minIncrementForUnique(self, A):
        A.sort()
        ans = 0
        for i in range(1, len(A)):
            if A[i] > A[i - 1]: continue
            ans += A[i - 1] - A[i] + 1
            A[i] = A[i - 1] + 1
        return ans

class Solution:
    def minIncrementForUnique(self, A):
        res = need = 0
        for i in sorted(A):
            res += max(need - i, 0)
            need = max(need + 1, i + 1)

        return res
        
        
        
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        res = 0
        for i in range(1, len(A)):
            if A[i] <= A[i-1]:
                res += A[i-1] + 1 - A[i]
                A[i] = A[i-1] + 1
        
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counter = Counter(A)
        to_place = []
        
        min_key = float('inf')
        for key in counter:
            min_key = min(min_key, key)
            if counter[key] > 1:
                for i in range(counter[key] - 1):
                    to_place.append(key)
                counter[key] = 1
        
        i = min_key
        moves = 0 
        to_place.sort(reverse=True)
        
        while to_place:
            if i not in counter and i > to_place[-1]:
                moves += i - to_place.pop()
            i += 1
        return moves
    
    # [3,2,1,2,1,7]
    
    # counter:{1:1, 2:1, 5:1, 7:1}
    # to_place =[5, 1]
    # i = 6
    # moves =  


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        A.append(100000)
        ans = taken = 0

        for i in range(1, len(A)):
            if A[i-1] == A[i]:
                taken += 1
                ans -= A[i]
            else:

                give = min(taken, A[i] - A[i-1] - 1)
                #print(give)
                ans += give * (give + 1) / 2 + give * A[i-1]
                taken -= give

        return int(ans)

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        A.sort()
        i = 1
        stack = []
        current = A[0]
        moves = 0
        while i < len(A):
            if A[i] == A[i-1]:
                stack.append(A[i])
            elif len(stack) > 0:
                for num in range(current + 1, A[i]):
                    moves += num - stack.pop()
                    if not stack:
                        break
            current = A[i]
            i += 1
        
        while stack:
            moves += current + 1 - stack.pop()
            current += 1
        return moves
                


import collections
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        res, need = 0, 0
        numCnt = collections.OrderedDict()
        for a in A:
            if a not in numCnt:
                numCnt[a] = 1
            else:
                numCnt[a] += 1
        while numCnt:
            num, count = numCnt.popitem(last=False)
            res += max((need - num)*count, 0) + count*(count-1)//2
            need = max(num, need) + count
            
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        ans = 0
        for i in range(1, len(A)):
            if i > 0 and A[i] <= A[i-1]:
                target = A[i-1] + 1
                ans += target - A[i]
                A[i] = target
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = 0
        A = sorted(A)

        for i in range(len(A) - 1):
            increment = max(0, A[i] - A[i + 1] + 1)
            A[i + 1] += increment
            count += increment

        return count

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if len(A) == 0:
            return 0
        A.sort()
        result = 0
        for i in range(1,len(A)):
            result += max(0, A[i-1] - A[i] + 1)
            A[i] += max(0, A[i-1] - A[i] + 1)
        return result

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if len(A) < 2:
            return 0
        A.sort()
        N = len(A)
        res = 0
        start = 0
        for i in range(1,N):
            if A[i] - A[start] >= i - start:
                start = i
            else:
                res += i-start-(A[i]-A[start])
        return res            
                


from typing import List
from collections import deque, Counter


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # print('-----')
        # print(f'A: {A}')

        cs = sorted([n, count] for n, count in list(Counter(A).items()))
        stack = deque(cs[::-1])
        # print(f'stack: {stack}')

        numOps = 0

        while stack:
            n, count = stack.pop()
            # print(f'n={n} count={count} numOps={numOps}', end=' ')
            numOps += count - 1
            if count > 1 and stack and stack[-1][0] == n + 1:
                stack[-1][1] += count - 1
                # print(f'move to {n+1, stack[-1][1]} stack={stack}')
            elif count > 1:
                stack.append([n+1, count-1])
                # print(f'upgrade to {n+1, count-1} stack={stack}')
            # else:
            #     print('')

        return numOps



class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        ans = 0
        hp, hp2 = [], []
        n, mina,maxa = len(A), min(A), max(A)
        seen = set()
        for a in A:
            if a not in seen:
                seen.add(a)
            else:
                heapq.heappush(hp, a)
        for i in range(mina + 1, maxa + n):
            if i not in seen:
                heapq.heappush(hp2, i)
        while hp:
            while hp2[0] <= hp[0]:
                heapq.heappop(hp2)
            ans += heapq.heappop(hp2) - heapq.heappop(hp)
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        A.sort()
        temp = A[0] 
        res = 0
        for i in range(1, len(A)):
            if A[i] > temp:
                temp = A[i]
            else:
                res += (temp+1-A[i])
                temp += 1
        return res
                
            


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        A_sum = sum(A)
        cnt = 0
        for i in range(1, len(A)):
            if A[i] <= A[i - 1]:
                cnt += (A[i] - A[i - 1] + 1)
                
                A[i] = A[i - 1] + 1
        return sum(A) - A_sum

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        A.sort()
        B=[A[0]]
        move=0
        for a in A[1:]:
            if a<=B[-1]:
                step=B[-1]-a+1
                move+=step
                a=a+step
            B.append(a)
                
        return move


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        ans = 0
        c = Counter(A)
        backlog = 0
        for i in range(min(A), max(A)+1):
            if i in c:
                backlog += c[i] - 1
            elif i not in c and backlog:
                ans += i
                backlog -= 1
        ans += sum(range(i+1, i+1+backlog))       
        return sum(c.keys()) + ans - sum(A)
        
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # A[i] is non negative 
        seen = set()
        replicates = []
        for i in A: #O(n)
            if i not in seen:
                seen.add(i)
            else:
                replicates.append(i)
        replicates.sort() #O(nlogn)
        res = 0
        next_candidates = 0
        while replicates: #O(n)
            num = replicates.pop(0)
            next_candidates = max(next_candidates, num)
            while next_candidates in seen:
                next_candidates += 1 
            seen.add(next_candidates)
            res += next_candidates - num 
        return res 

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A=sorted(A)
        ans=0
        if len(A)==0:
            return 0
        prev=A[0]
        i=1
        while i< len(A):
            if A[i]<=prev:
                ans+=prev-A[i]+1
                prev+=1
            else:
                prev=A[i]
            i+=1
        return ans
                


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        res = 0
        expect = 0
        for i in sorted(A):
            res += max(expect-i, 0)
            expect = max(i+1, expect+1)
        return res
        
        
        
        # import collections
        # cnt = collections.Counter(A)
        


import collections
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        res, need = 0, 0
        numCnt = collections.OrderedDict()
        for a in A:
            if a not in numCnt:
                numCnt[a] = 1
            else:
                numCnt[a] += 1
        print(numCnt, type(numCnt))
        while numCnt:
            num, count = numCnt.popitem(last=False)
            res += max((need - num)*count, 0) + count*(count-1)//2
            need = max(num, need) + count
            
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        dup = []
        seen = set()
        for i in A:
            if i not in seen:
                seen.add(i)
            else:
                dup.append(i)
        curr = 0
        j = 0
        i = -1
        ans = 0
        
        print(seen)
        while j < len(dup):
            if i ==dup[j]:
                curr = max(curr, i)
                while curr in seen:
                    curr +=1
                seen.add(curr)
                ans += curr - dup[j]
                j+=1
                
            else:
                i+=1
        return ans


from heapq import heappop, heappush, heapify
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        li=[]
        A.sort()
        n=len(A)
        if n==0:
            return 0
        used={}
        used[A[0]]=1
        for i in range(1,n):
            if A[i]==A[i-1]:
                li.append(A[i])
            else:
                used[A[i]]=1
        res=0
        t=A[0]
        for x in li:
            while used.get(t,0)!=0 or t<x:
                t+=1
            used[t]=1
            res+=t-x
        return res


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        dup = []
        seen = set()
        for i in A:
            if i not in seen:
                seen.add(i)
            else:
                dup.append(i)
        curr = 0
        j = 0
        i = -1
        ans = 0
        while j < len(dup):
            if i ==dup[j]:
                curr = max(curr, i)
                while curr in seen:
                    curr +=1
                seen.add(curr)
                ans += curr - dup[j]
                j+=1
                
            else:
                i+=1
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        def find(x):
            root[x] = find(root[x]+1) if x in root else x
            return root[x]
        root = {}
        return sum(find(i) - i for i in A)


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        res = 0

        for i in range(len(A)):
            if i > 0 and A[i] <= A[i-1]:
                res += ((A[i-1] + 1) - A[i])
                A[i] += ((A[i-1] + 1) - A[i])
        return res
        
            
                
            
            


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        roots = {}
        def find(k):
            roots[k] = k if k not in roots else find(roots[k] + 1)
            return roots[k]
        return sum(find(a) - a for a in A)

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        a = sorted(A)
        b = []
        
        if a == sorted(set(a)):
            return 0
        
        res = 0
        
        for i in range(0, len(a)-1):
            print('now: ', a[i], a[i+1])
            if a[i+1] == a[i]:
                a[i+1] += 1
                res += 1
            else:
                if a[i+1] < a[i]:
                    k = a[i] - a[i+1] + 1
                    a[i+1] += k
                    res += k
                    

        
        print(b)
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        diff = 0
        stack = []
        c = Counter(A)
        for i in range(min(c.keys()), max(c.keys())+1):
            if i in c:
                stack += [i] * (c[i] - 1)
            elif i not in c and stack:
                diff += i - stack.pop()
        return diff + sum(range(i+1, i+1+len(stack))) - sum(stack)


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        ans = 0
        for i, x in enumerate(A):
            if i >= 1:
                if A[i] <= A[i - 1]:
                    ans += A[i - 1] - A[i] + 1
                    A[i] = A[i - 1] + 1
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if len(A) < 2:
            return 0
        A.sort()
        ans, last = 0, A[0]-1
        for n in A:
            if n > last:
                last = n
            else:
                ans += (last-n+1)
                last += 1
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A or len(A) == 1:
            return 0
        
        ans = 0
        A.sort()
        for i in range(1,len(A)):
            if A[i-1] >= A[i]:
                gap = abs(A[i-1]-A[i]) + 1
                A[i] += gap
                ans += gap
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        n = len(A)
        if n < 2: return 0
        A.sort()
        avails = deque()
        for i in range(1, n):
            if A[i] > A[i - 1] + 1:
                avails.append([A[i - 1] + 1, A[i]])
            if i == n - 1:
                avails.append([A[i] + 1, A[i] + 2])
        l, r = avails.popleft()
        nexts = deque(range(l, r))
        r = nexts.popleft()
        pre = A[0]
        res = 0
        for i in range(1, n):
            if A[i] == pre:
                while r <= A[i]:
                    if nexts:
                        r = nexts.popleft()
                    elif avails:
                        l, r = avails.popleft()
                        nexts = deque(range(l, r))
                        r = nexts.popleft()
                    else:
                        r += 1
                res += r - A[i]
                A[i] = r
                if nexts:
                    r = nexts.popleft()
                elif avails:
                    l, r = avails.popleft()
                    nexts = deque(range(l, r))
                    r = nexts.popleft()
                else:
                    r += 1
            else:
                pre = A[i]
        return res

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:

    
        n = {}
        def find(x):
            n[x] = find(n[x] + 1) if x in n else x
            return n[x]
        return sum(find(a) - a for a in A)

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        n = {}
        ans = 0
        
        def find(j):
            n[j] = find(n[j]+1) if j in n else j
            return n[j]
        
        for i in A:         
            ans += find(i) - i
            #print (n[i])
        return ans
        


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:

    
        n = {}
        def find(x):
            if x in n:
                n[x] = find(n[x] + 1) 
            else:
                n[x] = x
            return n[x]
        ans = 0
        for a in A:
            ans += find(a) - a
        return ans

class Solution:
    def minIncrementForUnique(self, A):
        root = {}
        def find(x):
            root[x] = find(root[x] + 1) if x in root else x
            return root[x]
        return sum(find(a) - a for a in A)

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A = sorted(A)
        if not A:
            return 0
        
        k = A[0]
        moves = 0
        for i in range(1, len(A)):
            if A[i] <= k:
                moves += k + 1 - A[i]
                A[i] = k + 1
            k = A[i]
        return moves

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        answer = 0
        
        for i in range(1, len(A)):
            if A[i - 1] >= A[i]:
                answer += A[i - 1] - A[i] + 1
                A[i] += A[i - 1] - A[i] + 1
        
        return answer

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        res = need = 0
        for i in sorted(A):
            res += max(need - i, 0)
            need = max(need + 1, i + 1)
        return res

class Solution:
    def minIncrementForUnique(self, arr: List[int]) -> int:
        if not arr:
            return 0
        arr.sort()
        s, ans = arr[0], 0
        for i in arr:
            ans += max(0, s - i)
            s = max(s + 1, i + 1)
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if len(A)==0 or len(A)==1:
            return 0
        A.sort()
        cnt=0
        for i in range(1,len(A)):
            if A[i-1]>=A[i]:
                temp=A[i]
                A[i]=A[i-1]+1
                cnt+=A[i]-temp
        #print(A)
        return cnt

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        ret = 0
        for i in range(1, len(A)):
            p = A[i - 1]
            c = A[i]
            if p >= c:
                ret += p - c + 1
                A[i] = p + 1
        return ret

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if len(A)==0 or len(A)==1:
            return 0
        A.sort()
        cnt=0
        for i in range(1,len(A)):
            if A[i-1]>=A[i]:
                temp=A[i]
                A[i]=A[i-1]+1
                cnt+=A[i]-temp
        print(A)
        return cnt

from collections import defaultdict

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        H = defaultdict(int)
        for a in A:
            H[a] += 1
            
        V = sorted(H.keys())
        
        ans = 0
        while True:
            if len(H) == 0:
                return ans
            elif len(H) == 1:
                v = min(H.keys())
                ans += (H[v] - 1) * H[v] // 2
                del H[v]
                del V[0]
            else:
                v1, v2 = V[0], V[1]
                if v1 + H[v1] - 1 < v2:
                    ans += (H[v1] - 1) * H[v1] // 2
                    del H[v1]
                    del V[0]
                else:
                    ans += (v2 - v1 - 1) * (v2 - v1) // 2
                    ans += (H[v1] - v2 + v1) * (v2 - v1)
                    H[v2] += (H[v1] - v2 + v1)
                    del H[v1]
                    del V[0]
                    



class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A:
            return 0
        A.sort()
        results = 0
        prev = None
        for num in A:
            if prev != None and num <= prev:
                results += (prev + 1) - num
                prev = prev + 1
            else:
                prev = num
        return results

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A = sorted(A)
        
        nums = set()
        move = 0
        prev = -1
        for i in range(len(A)):
            cur_num = A[i]
            if cur_num <= prev:
                cur_num = prev + 1
            while cur_num in nums:
                cur_num += 1
            nums.add(cur_num)
            move += (cur_num - A[i])
            prev = cur_num
            
            
        return move

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        current=0
        res=0
        for i in range(len(A)):
            if A[i]<=current:
                res+=current-A[i]
                current=current+1
            else:
                current=A[i]+1
        return res


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        # sort and traverse 93.88%
        A.sort()
        count = 0
        
        for i in range(1, len(A)):
            if A[i] <= A[i - 1]:
                residual = A[i - 1] - A[i] + 1
                A[i] += residual
                count += residual
        
        return count
                
        
        # naive solution TLE O(n^2)
#         visited = set()
#         count = 0
        
#         for num in A:
#             if num in visited:
#                 while num in visited:
#                     num += 1
#                     count += 1
#             visited.add(num)
        
#         return count


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        count = 0
        
        for i in range(1, len(A)):
            if A[i] <= A[i - 1]:
                residual = A[i - 1] - A[i] + 1
                A[i] += residual
                count += residual
        
        return count
                
        
        # naive solution TLE O(n^2)
#         visited = set()
#         count = 0
        
#         for num in A:
#             if num in visited:
#                 while num in visited:
#                     num += 1
#                     count += 1
#             visited.add(num)
        
#         return count


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        moves = 0
        for i in range(1, len(A)):
            if A[i] <= A[i-1]:
                moves += A[i-1]+1 - A[i]
                A[i] = A[i-1]+1
            prev = A[i]
        return moves


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
      
        # while nums:
        #     for i in range(1,len(nums)+1):
        #         if i == len(nums): return step
        #         if nums[i] <= nums[i-1]:
        #             step += nums[i-1] - nums[i] + 1
        #             nums[i] += nums[i-1] - nums[i] + 1
        #             nums = nums[i:]
        #             break
        # return step
        step = curr = 0
        
        for e in sorted(A):
           
            step += max(curr-e, 0)
            curr = max(curr, e)+1
        return step
            
                


from collections import defaultdict
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        
        histogram = defaultdict(int)
        for num in A:
            histogram[num] += 1
        
        count = 0
        taken = []
        for num in range(0, 100000):
            if num in histogram and histogram[num] > 1:
                taken += [num] * (histogram[num] - 1)
            elif taken and num not in histogram:
                count += num - taken.pop()
        return count


from collections import defaultdict

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:

        A.sort()
        to_merge = []
        moves = 0
        for i in range(1, len(A)):
            if A[i] == A[i-1]:
                to_merge.append(A[i])
            elif to_merge:
                j = A[i-1]
                for j in range(A[i-1] + 1, A[i]):
                    m = to_merge.pop(0)
                    moves += (j - m)
                    if not to_merge:
                        break
        if to_merge:
            j = A[-1] + 1        
            while to_merge:
                m = to_merge.pop(0)
                moves += (j - m)
                j += 1
            
        return moves


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        
        if A == []:
            return 0
        else:
            A.sort()
            pre_item = A[0]
            moves = 0
            for i in range(1, len(A)):
                cur_item = A[i]
                if (A[i] < pre_item) or (A[i] == pre_item):

                    moves = moves + pre_item + 1 - A[i]
                    A[i] = pre_item + 1
                pre_item = A[i]
            return moves

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        rez = 0

        for index in range(1, len(A)):
            if A[index - 1] >= A[index]:
                rez += A[index - 1] - A[index] + 1
                A[index] = A[index - 1] + 1

        return rez


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        if not A: return 0
        repeat = collections.deque()
        A = sorted(A)
        for i,v in enumerate(A):
            if i and v == A[i-1]:
                repeat.append(v)
        slots = sorted(list(set(list(range(A[0],A[-1] + 1))) - set(A)))
        res = 0
        for i in slots:
            if repeat and i > repeat[0]:
                res += i - repeat[0]
                repeat.popleft()
        return res - sum(repeat) + sum([i for i in range(A[-1]+1,A[-1]+1+len(repeat))])

class Solution:
    def minIncrementForUnique(self, A):
        res = need = 0
        for i in sorted(A):
            res += max(need - i, 0)
            need = max(need + 1, i + 1)
            print((res , need))
        return res
        
        
        
        


from collections import defaultdict

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count_for_val = defaultdict(lambda:0)
        dups = set()
        for i in A:
            count_for_val[i] += 1
            if count_for_val[i] > 1:
                dups.add(i)
        output = 0
        dups = sorted(dups)
        if not len(dups):
            return 0
        orig = dups[0]
        for dup in dups:
            count = count_for_val[dup] - 1
            while count > 0:
                orig += 1
                if orig > dup and orig not in count_for_val:
                    count_for_val[orig] = 1
                    output = output + (orig - dup)
                    count -= 1
        return output
        
                


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        ans = 0
        for i in range(1,len(A)):
            if(A[i-1]>=A[i]):
                ans += A[i-1]-A[i]+1
                A[i] += A[i-1]-A[i]+1
                
        return ans

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        root = {}
        def find(x):
            root[x] = find(root[x] + 1) if x in root else x
            return root[x]
        return sum(find(a) - a for a in A)

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count=collections.Counter(A)
        used=[]
        ans=0
        for x in range(41000):
            if count[x] >= 2:
                used.extend([x] * (count[x]-1))
            elif used and count[x]==0:
                ans+=x-used.pop()
        return ans

#         count = collections.Counter(A)
#         taken = []

#         ans = 0
#         for x in range(100000):
#             if count[x] >= 2:
#                 taken.extend([x] * (count[x] - 1))
#             elif taken and count[x] == 0:
#                 ans += x - taken.pop()
#         return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count=collections.Counter(A)
        used=[]
        ans=0
        for x in range(40500):
            if count[x] >= 2:
                used.extend([x] * (count[x]-1))
            elif used and count[x]==0:
                ans+=x-used.pop()
        return ans

#         count = collections.Counter(A)
#         taken = []

#         ans = 0
#         for x in range(100000):
#             if count[x] >= 2:
#                 taken.extend([x] * (count[x] - 1))
#             elif taken and count[x] == 0:
#                 ans += x - taken.pop()
#         return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
      
        # while nums:
        #     for i in range(1,len(nums)+1):
        #         if i == len(nums): return step
        #         if nums[i] <= nums[i-1]:
        #             step += nums[i-1] - nums[i] + 1
        #             nums[i] += nums[i-1] - nums[i] + 1
        #             nums = nums[i:]
        #             break
        # return step
        step = 0
        if not A or len(A) ==1: return step
        prev = float('-inf')
        nums = sorted(A)
        for e in nums:
            if e <= prev:
                step += prev-e + 1
                prev += 1
            else: prev = e
        return step
            
                


from collections import Counter
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        c=Counter(A)
        ans=0
        prev=-1
        for num in sorted(c):
            if num<=prev:
                ans+=(prev-num+1)*c[num]+(c[num]-1)*c[num]//2
                prev=num+(prev-num+1)+(c[num]-1)
            else:
                ans+=((c[num]-1)*c[num]//2)
                prev=num+(c[num]-1)
        return ans
                


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        c = Counter(A)
        print(c)
        res = need = 0
        for i in sorted(A):
            res += max(need - i, 0)
            need = max(need + 1, i + 1)
        return res

from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counts = Counter(A)
        taken = []
        ans = 0
        
        for num in range(41000):
            num_count = counts[num]
            if num_count >= 2:
                taken.extend([num] * (num_count - 1))
            elif taken and num_count == 0:
                ans += num - taken.pop()
                
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        dic = dict(collections.Counter(A))
        sortedDic = sorted(list(dic.items()), key=lambda x: x[0])
        
        result = 0
        
        while sortedDic:
            num, freq = sortedDic.pop(0)
            if freq > 1:
                diff = freq - 1
                
                if sortedDic and sortedDic[0][0] == num + 1:
                    sortedDic[0] = (num + 1, diff + sortedDic[0][1])
                else:
                    sortedDic.insert(0, (num + 1, diff))
                
                result += diff
        
        return result
                
                


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        #
        count = collections.Counter(A)
        to_move = []
        num_moves = 0
        end = 50000
        
        for i in range(end):
            if count[i] >= 2:
                to_move.extend([i] * (count[i] - 1))
            elif to_move and count[i] == 0:
                num_moves += i - to_move.pop()
        
        return num_moves
            


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        #O(n) T | O(n) S
        count = collections.Counter(A)
        to_move = []
        num_moves = 0
        end = 50000
        
        for i in range(end):
            if count[i] >= 2:
                to_move.extend([i] * (count[i] - 1))
            elif to_move and count[i] == 0:
                num_moves += i - to_move.pop()
        
        return num_moves
            


from collections import Counter

class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        counts = Counter(A)
        taken = []
        ans = 0
        
        for num in range(50001):
            num_count = counts[num]
            if num_count >= 2:
                taken.extend([num] * (num_count - 1))
            elif taken and num_count == 0:
                ans += num - taken.pop()
                
        return ans


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        count = collections.Counter(A)
        taken = []
        moves = 0
        
        for i in range(45000):
            c = count[i]
            if c >= 2:
                taken += (c-1) * [i]
            elif len(taken) > 0 and c == 0:
                moves += i - taken.pop()
        
        return moves
        
            
            


class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        cnt = [0 for i in range(80001)]
        minv, ans, n = 40001, 0, len(A)
        for i in A:
            cnt[i] += 1
            minv = min(minv, i)
        for i in range(minv, 80001):
            if not n:
                break
            if cnt[i] > 1:
                cnt[i + 1] += cnt[i] - 1
                ans += cnt[i] - 1
            if cnt[i] == 1:
                n -= 1
        return ans