from collections import defaultdict as DD from heapq import * def main(): n = int(input()) A = list(map(int, input().split())) P = sorted(set(A)) ans = 0 D = DD(int) E = DD(int) hq = [] for a in A: D[a] += 1 pi = 1 now = P[0] X = [[0, 1<<30]] le = 0 while 1: cnt = D[now] #print(now, ans) for _ in range(cnt): if E[now] == 0: E[now] = 1 if not E[now-1]: heappush(hq, -now) else: D[now+1] += 1 nxt = -heappop(hq) ans += now-nxt+1 E[nxt] = 0 E[nxt-1] = 1 if not E[nxt-2]: heappush(hq, -(nxt-1)) if E[nxt+1]: heappush(hq, -nxt-1) if D[now+1] != 0: now += 1 if pi < len(P) and P[pi] == now: pi += 1 else: if pi == len(P): break nxt = P[pi] pi += 1 now = nxt return ans print(main())