Colonel has n badges. He wants to give one badge to every of his n soldiers. Each badge has a coolness factor, which shows how much it's owner reached. Coolness factor can be increased by one for the cost of one coin. 

For every pair of soldiers one of them should get a badge with strictly higher factor than the second one. Exact values of their factors aren't important, they just need to have distinct factors. 

Colonel knows, which soldier is supposed to get which badge initially, but there is a problem. Some of badges may have the same factor of coolness. Help him and calculate how much money has to be paid for making all badges have different factors of coolness.


-----Input-----

First line of input consists of one integer n (1 ≤ n ≤ 3000).

Next line consists of n integers a_{i} (1 ≤ a_{i} ≤ n), which stand for coolness factor of each badge.


-----Output-----

Output single integer — minimum amount of coins the colonel has to pay.


-----Examples-----
Input
4
1 3 1 4

Output
1
Input
5
1 2 3 2 5

Output
2


-----Note-----

In first sample test we can increase factor of first badge by 1.

In second sample test we can increase factors of the second and the third badge by 1.

Source: codeforces | Difficulty: EASY
Tags: Complete search

Sorting

Implementation

Greedy algorithms


Solutions:
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
seen = {}
cost = 0
for i in range(len(arr)):
	cur = arr[i]
	if cur in seen:
		found = False
		val = cur + 1
		cost += 1
		while not found:
			if val not in seen:
				seen[val] = True
				found = True
			else:
				val += 1
				cost += 1
	else:
		seen[cur] = True
print(cost)


n = int(input())
l = list(map(int, input().split()))
l.sort()
c = 0
for i in range(n - 1):
	a = l[0:i + 1]
	while l[i + 1] in a:
		l[i + 1] = l[i + 1] + 1
		c += 1
print(c)


n = int(input())
a = sorted(map(int, input().split()))
cost = 0
for i in range(1, n):
	if a[i - 1] >= a[i]:
		cost += a[i - 1] - a[i] + 1
		a[i] = a[i - 1] + 1
print(cost)


n = int(input())
arr = list(map(int, input().split()))
used = [0] * 7005
arr.sort()
res = 0
for i in range(n):
	if not used[arr[i]]:
		used[arr[i]] = 1
	else:
		for j in range(arr[i], 7001):
			if not used[j]:
				used[j] = 1
				break
			else:
				res += 1
print(res)


n = int(input())
ls = list(map(int, input().split()))
ls.sort()
ans = 0
for i in range(1, len(ls)):
	if ls[i] <= ls[i - 1]:
		tmp = ls[i - 1] - ls[i]
		ans += 1 + tmp
		ls[i] = ls[i] + tmp + 1
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import math

def fact(x):
	if x == 0:
		return 1
	else:
		return x * fact(x - 1)

def lower_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] >= num:
			answer = middle
			end = middle - 1
		else:
			start = middle + 1
	return answer

def upper_bound(li, num):
	answer = -1
	start = 0
	end = len(li) - 1
	while start <= end:
		middle = (end + start) // 2
		if li[middle] <= num:
			answer = middle
			start = middle + 1
		else:
			end = middle - 1
	return answer

def abs(x):
	return x if x >= 0 else -x
cnt = dict()
for t in range(1):
	n = int(input())
	badges = list(map(int, input().split()))
	for i in range(1, 2 * n):
		cnt.setdefault(i, 0)
	for i in badges:
		cnt[i] += 1
	li0 = []
	li = []
	for (k, v) in list(cnt.items()):
		if v == 0:
			li0.append(k)
		elif v >= 2:
			li.append(k)
	sumi = 0
	for i in li:
		check = 0
		for j in range(cnt[i] - 1):
			while True:
				if li0[check] > i:
					sumi += li0[check] - i
					li0.pop(check)
					check = 0
					break
				else:
					check += 1
	print(sumi)


import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000)
from collections import Counter

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def val():
	return int(input().rstrip('\n'))

def st():
	return input().rstrip('\n')

def sttoli():
	return [int(i) for i in input().rstrip('\n')]

def notinarun(a, b, c):
	(x0, x1, y0, y1, z0, z1) = (min(a[0], b[0]), max(a[0], b[0]), min(a[1], b[1]), max(a[1], b[1]), min(a[2], b[2]), max(a[2], b[2]))
	if x0 <= c[0] <= x1 and y0 <= c[1] <= y1 and (z0 <= c[2] <= z1):
		return False
	return True
n = val()
l = li()
cnt = Counter(l)
mi = min(l)
ma = max(l)
tot = 0
i = mi
while i <= ma:
	if cnt[i] > 1:
		tot += cnt[i] - 1
		cnt[i + 1] += cnt[i] - 1
	if i + 1 in cnt and i + 1 > ma and cnt[i + 1]:
		ma = max(ma, i + 1)
	i += 1
print(tot)


n = int(input())
a = [int(i) for i in input().split()]
b = dict()
for i in range(len(a)):
	if a[i] not in b:
		b.update({a[i]: a.count(a[i])})
a = sorted(list(b))
i = h = 0
while i < len(a):
	if b[a[i]] > 1:
		if a[i] + 1 in b:
			b[a[i] + 1] += b[a[i]] - 1
			h += b[a[i]] - 1
			b[a[i]] = 1
		else:
			h += b[a[i]] - 1
			b.update({a[i] + 1: b[a[i]] - 1})
			a = sorted(list(b))
	i += 1
print(h)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = sum(a)
for i in range(1, n):
	if a[i] <= a[i - 1]:
		a[i] = a[i - 1] + 1
print(sum(a) - ans)


n = int(input())
y = []
y = [int(k) for k in input().split(' ')]
y = sorted(y)
i = x = count = 0
while i < n - 1:
	if y[i] >= y[i + 1]:
		x = x + (y[i] - y[i + 1]) + 1
		y[i + 1] = y[i] + 1
	i = i + 1
print(x)


n = int(input())
cnt = dict()
A = list(map(int, input().split()))
for x in A:
	if x not in cnt:
		cnt[x] = 0
	cnt[x] += 1
ans = 0
for i in range(1, 2 * n + 1):
	if i in cnt:
		for j in range(cnt[i] - 1):
			ans += 1
			if i + 1 not in cnt:
				cnt[i + 1] = 0
			cnt[i + 1] += 1
print(ans)


n = input()
n = int(n)
c = 0
b = input()
b = b.split(' ')
b = map(int, b)
b = sorted(b)
for i in range(1, n):
	if b[i] == b[i - 1]:
		b[i] = b[i] + 1
		c = c + 1
	elif b[i] < b[i - 1]:
		d = b[i - 1] - b[i]
		b[i] = b[i] + d + 1
		c = c + d + 1
print(c)


n = int(input())
list = input().split(' ')
numbers = []
for i in list:
	numbers.append(int(i))
numbers.sort()
max = numbers[-1]
badges = []
for i in range(max):
	badges.append(0)
for i in numbers:
	badges[i - 1] += 1
count = 0
for i in range(len(badges) - 1):
	if badges[i] == 0 or badges[i] == 1:
		continue
	else:
		temp = badges[i]
		badges[i] = 1
		badges[i + 1] += temp - 1
		count += temp - 1
if badges[-1] > 1:
	count += int(badges[-1] * (badges[-1] - 1) / 2)
print(count)


n = int(input())
a = list(map(int, input().split()))
b = sorted(a)
x = 0
for i in range(1, n):
	if b[i] <= b[i - 1]:
		x += b[i - 1] - b[i] + 1
		b[i] = b[i - 1] + 1
print(x)


n = int(input())
bs = sorted(list(map(int, input().split())))
ans = 0
al = []
for i in range(n):
	if bs[i] in al:
		ans += al[-1] - bs[i] + 1
		al.append(al[-1] + 1)
	elif bs[i] not in al:
		al.append(bs[i])
		al = sorted(al)
print(ans)


n = int(input())
x = [int(q) for q in input().split()]
y = sorted(x)
c = 0
for i in range(0, len(y) - 1):
	while y[i + 1] <= y[i]:
		y[i + 1] += 1
		c += 1
print(c)


MyBadges = [0] * 6000
(N, Counter) = (int(input()), 0)
for i in list(map(int, input().split())):
	MyBadges[i] += 1
for i in range(6000):
	if MyBadges[i] >= 1:
		while MyBadges[i] != 1:
			Index = MyBadges[i:].index(0)
			Counter += Index
			MyBadges[Index + i] = 1
			MyBadges[i] -= 1
print(Counter)


n = int(input())
a = list(map(int, input().split()))
a.sort()
c = 0
for i in range(1, n):
	if a[i] < a[i - 1]:
		x = a[i - 1] - a[i] + 1
		a[i] = a[i] + x
		c = c + x
	elif a[i] == a[i - 1]:
		a[i] = a[i] + 1
		c = c + 1
print(c)


n = int(input())
s = list(map(int, input().split()))
t = [0 for i in range(6001)]
for i in range(len(s)):
	t[s[i]] += 1
ans = 0
for i in range(6001):
	if t[i] > 1:
		ans += t[i] - 1
		t[i + 1] += t[i] - 1
print(ans)


n = int(input())
l = input().split(' ')
m = list(map(int, l))
m.sort()
sum = 0
for i in range(len(m) - 1):
	for j in range(i + 1, len(m)):
		if m[i] == m[j]:
			m[j] = m[j] + 1
			sum = sum + 1
print(sum)


n = int(input())
x = 0
arr = sorted([int(z) for z in input().split()])
for i in range(n - 1):
	if arr[i] >= arr[i + 1]:
		p = arr[i] - arr[i + 1]
		arr[i + 1] += p + 1
		x += p + 1
print(x)


n = int(input())
a = list(sorted(map(int, input().split())))
ans = 0
for i in range(1, n):
	if a[i] <= a[i - 1]:
		ans += a[i - 1] - a[i] + 1
		a[i] = a[i - 1] + 1
print(ans)


n = int(input())
a = sorted(map(int, input().split()))
ans = 0
for i in range(1, n):
	ans += max(0, a[i - 1] + 1 - a[i])
	a[i] = max(a[i - 1] + 1, a[i])
print(ans)


__author__ = 'artyom'
n = int(input())
a = sorted(map(int, input().split()))
(c, p) = (0, 0)
for x in a:
	if x <= p:
		c += p - x + 1
		p += 1
	else:
		p = x
print(c)


n = int(input())
l_n = list(map(int, input().split()))
f_a = [0] * 6000
for t_n in l_n:
	f_a[t_n] += 1
t = 0
c_n = 0
for i in range(6000):
	t += c_n
	if f_a[i] > 1:
		c_n += f_a[i] - 1
	elif f_a[i] == 0 and c_n > 0:
		c_n -= 1
print(t)


import sys
from collections import defaultdict
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())

def main():
	d = inp()
	v = inlt()
	v.sort()
	c = 0
	for i in range(1, d):
		if v[i] == v[i - 1]:
			v[i] += 1
			c += 1
		elif v[i] < v[i - 1]:
			c += v[i - 1] - v[i] + 1
			v[i] = v[i - 1] + 1
	print(c)
main()


import sys
import random
from math import log2, log, ceil
input = sys.stdin.readline

def swaparr(arr, a, b):
	temp = arr[a]
	arr[a] = arr[b]
	arr[b] = temp

def gcd(a, b):
	if a > 0:
		return gcd(b % a, a)
	return b

def primefs(n):
	if n == 1:
		return 1
	primes = {}
	while n % 2 == 0:
		primes[2] = primes.get(2, 0) + 1
		n = n // 2
	for i in range(3, int(n ** 0.5) + 2, 2):
		while n % i == 0:
			primes[i] = primes.get(i, 0) + 1
			n = n // i
	if n > 2:
		primes[n] = primes.get(n, 0) + 1
	return primes

def swap(a, b):
	temp = a
	a = b
	b = temp
	return (a, b)

def find(x, link):
	while x != link[x]:
		x = link[x]
	return x

def union(x, y, size, link):
	x = find(x, link)
	y = find(y, link)
	if size[x] < size[y]:
		(x, y) = swap(x, y)
	if x != y:
		size[x] += size[y]
		link[y] = x

def sieve(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for i in range(p * p, n + 1, p):
				prime[i] = False
		p += 1
	return prime
MAXN = int(1000000.0 + 5)

def spf_sieve():
	spf[1] = 1
	for i in range(2, MAXN):
		spf[i] = i
	for i in range(4, MAXN, 2):
		spf[i] = 2
	for i in range(3, ceil(MAXN ** 0.5), 2):
		if spf[i] == i:
			for j in range(i * i, MAXN, i):
				if spf[j] == j:
					spf[j] = i

def factoriazation(x):
	ret = {}
	while x != 1:
		ret[spf[x]] = ret.get(spf[x], 0) + 1
		x = x // spf[x]
	return ret

def int_array():
	return list(map(int, input().split()))
MOD = int(1000000000.0) + 7
CMOD = 998244353
INF = float('inf')
NINF = -float('inf')
n = int(input())
a = sorted(int_array())
ans = 0
m_set = set()
for i in a:
	if i not in m_set:
		m_set.add(i)
	else:
		i += 1
		ans += 1
		while i in m_set:
			i += 1
			ans += 1
		m_set.add(i)
print(ans)


n = int(input())
badges = [int(i) for i in input().split()]
badges.sort()
cnt = [0] * 7000
m = len(cnt)
c = 0
for e in badges:
	cnt[e] += 1
for i in range(m):
	j = i
	aux = 0
	while cnt[i] > 1:
		while cnt[j] > 0:
			aux += 1
			j += 1
			if j == m:
				break
		c += aux
		cnt[j] = 1
		cnt[i] -= 1
print(c)


n = int(input())
a = [int(i) for i in input().split()]
hashi = [0] * (n * 2)
for i in a:
	hashi[i] += 1
ans = 0
for i in range(1, 2 * n):
	if hashi[i] - 1 > 0:
		hashi[i + 1] += hashi[i] - 1
		ans += hashi[i] - 1
print(ans)


n = int(input())
a = list(map(int, input().split()))
r = list(set(a))
d = dict()
a.sort()
r.sort()
k = 0
for i in range(len(r)):
	x = a.count(r[i])
	d[r[i]] = x
if n == len(r):
	print(0)
else:
	c = 0
	for i in range(len(r)):
		if d[r[i]] > 1:
			k = d[r[i]] - 1
			t = 0
			for j in range(r[i] + 1, 10001):
				if t == k:
					break
				if j in r:
					pass
				else:
					r.append(j)
					c = c + abs(j - r[i])
					t = t + 1
	print(c)


n = int(input())
A = list(map(int, input().split()))
C = [0] * (2 * n + 2)
for a in A:
	C[a] += 1
ans = c = 0
for i in range(2 * n + 2):
	ans += c
	if C[i] > 1:
		c += C[i] - 1
	if C[i] == 0 and c > 0:
		c -= 1
print(ans)


n = int(input())
k = list(sorted(map(int, input().split())))
s = 0
for i in range(n - 1):
	for j in range(i + 1, n):
		if k[j] != k[i]:
			break
		s += 1
		k[j] += 1
		j += 1
print(s)


num_badges = int(input())
badges = list(map(int, input().split()))
badges.sort()
carry = 0
solution = 0
for (pos, badge) in enumerate(badges):
	result = pos + 1 + carry - badge
	solution += max(0, result)
	carry += max(-1 * result, 0)
print(solution)


n = int(input())
a = sorted([*map(int, input().split())])
num = [0] * 6001
for i in a:
	num[i] += 1
ans = 0
f = True
i = 0
while f:
	if num[i] > 1:
		num[i + 1] += num[i] - 1
		ans += num[i] - 1
		num[i] = 1
	f = len([*filter(lambda x: x > 0, num[i:])]) != 0
	i += 1
i -= 1
print(ans + num[i] * (num[i] + 1) // 2)


from bisect import bisect_right
n = int(input())
l = [int(x) for x in input().split()]
l2 = l
l2 = set(l2)
if len(l2) == n:
	print(0)
else:
	temp = []
	for i in range(1, n + 1):
		if i not in l2:
			temp.append(i)
	for i in range(n + 1, n * 3):
		temp.append(i)
	temp.sort()
	temp = set(temp)
	d = {}
	ans = {}
	for i in l:
		if i not in d:
			d[i] = 1
		else:
			d[i] += 1
	for i in d.keys():
		if d[i] != 1:
			ans[i] = d[i]
	c = 0
	for i in ans.keys():
		r = ans[i]
		while r > 1:
			temp = list(temp)
			m = temp[bisect_right(temp, i)]
			c += m - i
			r -= 1
			temp = set(temp)
			temp.remove(m)
	print(c)


n = int(input())
badges = list(map(int, input().split()))
badges = sorted(badges)
count = 0
for i in range(1, n):
	if badges[i] == badges[i - 1]:
		badges[i] += 1
		count += 1
	elif badges[i] < badges[i - 1]:
		diff = badges[i - 1] - badges[i]
		badges[i] += diff
		count += diff
		badges[i] += 1
		count += 1
print(count)


import string
import math
from collections import Counter

def array_int():
	return [int(i) for i in input().split()]

def vary(number_of_variables):
	if number_of_variables == 1:
		return int(input())
	if number_of_variables >= 2:
		return map(int, input().split())

def makedict(var):
	return dict(Counter(var))
mod = 1000000007
n = vary(1)
num = array_int()
num.sort()
count = 0
for i in range(n):
	for j in range(i + 1, n):
		if num[i] == num[j]:
			num[j] += 1
			count += 1
print(count)


n = int(input())
l = list(map(int, input().split()))
l.sort()
ans = 0
d = {}
for j in l:
	d[j] = d.get(j, 0) + 1
for t in range(n):
	while d.get(l[t], 0) > 1:
		d[l[t]] = d.get(l[t], 0) - 1
		l[t] += 1
		d[l[t]] = d.get(l[t], 0) + 1
		ans += 1
print(ans)


n = int(input())
s1 = list(map(int, input().split()))
s1.sort()
count = 0
temp = 0
for i in range(n - 1):
	if s1[i] >= s1[i + 1]:
		temp = s1[i + 1]
		s1[i + 1] = s1[i] + 1
		count = count + s1[i] - temp + 1
print(count)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	res = 0
	for i in range(n - 1):
		if a[i] >= a[i + 1]:
			x = a[i + 1]
			a[i + 1] += a[i] - a[i + 1] + 1
			res += a[i] - x + 1
	print(res)
solve()


n = int(input())
L = [int(x) for x in input().split()]
L.sort()
cost = 0
con = True
while con:
	con = False
	for i in range(n - 1, 0, -1):
		if L[i] == L[i - 1]:
			L[i] += 1
			cost += 1
			con = True
print(cost)


nb_badges = int(input())
badges = sorted([int(x) for x in input().split()])
curr = 0
csum = 0
for x in sorted(badges):
	curr = max(curr + 1, x)
	csum += curr
print(csum - sum(badges))


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
z = Counter(l)
ans = 0
i = 1
while z != {}:
	if i in z and z[i] > 1:
		ans += z[i] - 1
		z[i + 1] += z[i] - 1
	del z[i]
	i += 1
print(ans)


import math
from operator import itemgetter

def get_primes(prime_supr):
	is_prime = [0] * 2 + [1] * prime_supr
	for i in range(2, int(math.sqrt(prime_supr)) + 1):
		if is_prime[i]:
			for j in range(i * i, prime_supr + 1, i):
				is_prime[j] = 0
	return is_prime
get_int = lambda : map(int, input().split())
n = int(input())
a = list(get_int())
ans = 0
a.sort()
for i in range(1, n):
	if a[i] <= a[i - 1]:
		ans += a[i - 1] - a[i] + 1
		a[i] = a[i - 1] + 1
print(ans)


t = int(input())
arr = list(map(int, input().split()))
arr = sorted(arr)
count = 0
for i in range(1, t):
	if arr[i] <= arr[i - 1]:
		count += abs(arr[i] - arr[i - 1]) + 1
		arr[i] = arr[i - 1] + 1
print(count)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, copy
from itertools import chain, dropwhile, permutations, combinations
from collections import defaultdict, deque

def VI():
	return list(map(int, input().split()))

def I():
	return int(input())

def LIST(n, m=None):
	return [0] * n if m is None else [[0] * m for i in range(n)]

def ELIST(n):
	return [[] for i in range(n)]

def MI(n=None, m=None):
	if n is None:
		(n, m) = VI()
	arr = LIST(n)
	for i in range(n):
		arr[i] = VI()
	return arr

def MS(n=None, m=None):
	if n is None:
		(n, m) = VI()
	arr = LIST(n)
	for i in range(n):
		arr[i] = input()
	return arr

def MIT(n=None, m=None):
	if n is None:
		(n, m) = VI()
	a = MI(n, m)
	arr = LIST(m, n)
	for (i, l) in enumerate(a):
		for (j, x) in enumerate(l):
			arr[j][i] = x
	return arr

def run(n, a):
	a.sort()
	ans = 0
	for i in range(n - 1):
		while a[i + 1] <= a[i]:
			a[i + 1] += 1
			ans += 1
	print(ans)

def main(info=0):
	n = I()
	a = VI()
	run(n, a)
main()


n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
sum = 0
k = l[0]
for i in range(1, len(l)):
	if k >= l[i]:
		k += 1
	else:
		k = l[i]
	sum += k - l[i]
print(sum)


def main():
	n = int(input())
	l = [0] * (n + 1)
	for a in map(int, input().split()):
		l[a] += 1
	res = s = 0
	for (i, x) in enumerate(l):
		if x > 1:
			x -= 1
			res -= i * x
			s += x
		elif not x and s:
			res += i
			s -= 1
	res += s * (n * 2 + s + 1) // 2
	print(res)
main()


import sys
from collections import defaultdict
n = int(input())
a = list(map(int, sys.stdin.readline().split()))
d = defaultdict(int)
for i in a:
	d[i] += 1
ans = 0
for i in range(1, 2 * n + 1):
	if d[i] > 0:
		delta = d[i] - 1
		ans += delta
		d[i + 1] += delta
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
badges = set()
for badge in a:
	if badge not in badges:
		badges.add(badge)
	else:
		i = 0
		while badge + i in badges:
			i += 1
		badges.add(badge + i)
		ans += i
print(ans)


n = int(input())
k = list(sorted(map(int, input().split())))
numbers = [0] * (3 * n)
for ki in k:
	numbers[ki] += 1
s = 0
for i in range(len(numbers)):
	if numbers[i] > 1:
		ds = numbers[i] - 1
		numbers[i + 1] += ds
		numbers[i] = 1
		s += ds
print(s)


n = int(input())
ar = list(map(int, input().split()))
ar.sort()
cnt = 0
for i in range(n - 1):
	if ar.count(ar[i]) > 1:
		if ar[i] + 1 not in ar:
			cnt += 1
			ar[i] += 1
		else:
			while True:
				if ar[i] + 1 in ar:
					cnt += 1
					ar[i] += 1
				else:
					ar[i] += 1
					cnt += 1
					break
print(cnt)


n = int(input())
array = [int(i) for i in input().split()]
array = sorted(array)
sum = 0
for i in range(1, n):
	if array[i] <= array[i - 1]:
		sum += array[i - 1] - array[i] + 1
		array[i] += array[i - 1] - array[i] + 1
print(sum)


from sys import stdin, stdout
n = int(stdin.readline())
a = list(map(int, stdin.readline().split()))
a.sort()
memo = {}
for i in range(n):
	if a[i] not in memo:
		memo[a[i]] = 1
	else:
		memo[a[i]] += 1
coins = 0
while max(memo.values()) != 1:
	for (key, value) in memo.items():
		if value == 1:
			continue
		else:
			count = 1
			for _ in range(value - 1):
				if key + count not in memo:
					memo[key + count] = 1
				else:
					memo[key + count] += 1
				coins += count
				count += 1
			memo[key] = 1
			break
print(coins)


n = int(input())
a = input()
A = []
Sum = 0
for i in a.split():
	A.append(int(i))
A.sort()
for j in range(0, n):
	for k in range(j + 1, n):
		if A[j] == A[k]:
			A[k] = A[k] + 1
			Sum = Sum + 1
		else:
			continue
print(Sum)


x = int(input())
y = list(map(int, input().split(' ')))
y.sort()
c = y[0]
add = 0
for i in range(1, x):
	if y[i] > c:
		c = y[i]
	else:
		c = c + 1
		add += c - y[i]
print(add)


n = int(input())
a = list(map(int, input().split()))
a.sort()
coins = 0
for i in range(n):
	if i - 1 >= 0 and a[i] <= a[i - 1]:
		coins += a[i - 1] - a[i] + 1
		a[i] = a[i - 1] + 1
print(coins)


input()
(pr, v) = (0, 0)
for a in sorted(map(int, input().split())):
	v += max(0, pr - a + 1)
	pr = max(pr + 1, a)
print(v)


n = int(input())
l = sorted(list(map(int, input().split())))
d = l[:]
s = 0
for i in range(1, n):
	if l[i] <= l[i - 1]:
		l[i] = l[i - 1] + 1
for i in range(n):
	s += abs(l[i] - d[i])
print(s)


n = int(input())
list = [int(i) for i in input().split()]
list.sort()
cnt = 0
for i in range(1, n):
	if list[i - 1] >= list[i]:
		cnt += abs(list[i] - list[i - 1]) + 1
		list[i] += abs(list[i] - list[i - 1]) + 1
print(cnt)


import sys
n = int(input())
if n == 1:
	print(0)
	return
l = list(map(int, input().split(' ')))
l.sort()
min = l[0]
val = 0
for i in range(1, len(l)):
	if l[i] <= l[i - 1]:
		val += 1 + l[i - 1] - l[i]
		l[i] += 1 + l[i - 1] - l[i]
print(val)


n = int(input())
a = [int(c) for c in input().split()]
a = sorted(a)
cost = 0
for i in range(n):
	if i > 0:
		if a[i] <= a[i - 1]:
			add = a[i - 1] - a[i] + 1
			a[i] += add
			cost += add
print(cost)


from math import *
c = 0
n = int(input())
a = list(map(int, input().split()))
a.sort()
for i in range(1, n):
	if a[i - 1] == a[i]:
		a[i] = a[i] + 1
		c += 1
	elif a[i - 1] > a[i]:
		c += a[i - 1] - a[i] + 1
		a[i] = a[i - 1] + 1
print(c)


n = int(input())
a = list(map(int, input().split()))
a.sort()
i = 0
c = 0
while i < n - 1:
	if a[i] >= a[i + 1]:
		c += a[i] + 1 - a[i + 1]
		a[i + 1] = a[i] + 1
	i += 1
print(c)


n = int(input())
l = list(map(int, input().split()))
l.sort()
count = 0
for i in range(n - 1):
	if l[i] >= l[i + 1]:
		x = l[i + 1]
		l[i + 1] = l[i] + 1
		count += l[i + 1] - x
print(count)


n = int(input())
badges = [int(i) for i in input().split()]
badges.sort()
diff = []
coins = 0
for m in range(1, n):
	diff.append(badges[m] - badges[m - 1])
i = 0
while any((n <= 0 for n in diff)):
	i += 1
	if i > n:
		i = 0
	small_diff = badges[i] - badges[i - 1]
	if small_diff <= 0:
		badges[i] = badges[i] - small_diff + 1
		coins += -small_diff + 1
	diff.clear()
	for m in range(1, n):
		diff.append(badges[m] - badges[m - 1])
print(coins)


n = int(input())
arr = list(map(int, input().split()))
count = [0] * 6002
m = 1
for i in range(n):
	count[arr[i]] += 1
	m = max(m, arr[i])
ans = []
for i in range(1, 6002):
	if count[i] == 0:
		ans.append(i)
s = 0
ind = 0
for i in range(1, m + 1):
	if count[i] != 0:
		while count[i] != 1:
			if ans[ind] > i:
				s += ans[ind] - i
				count[i] -= 1
			ind += 1
print(s)


n = int(input())
a = input()
a = a.split()
for i in range(n):
	a[i] = int(a[i])
a = sorted(a)
pre = 0
ans = 0
for i in range(n):
	if a[i] <= pre:
		ans = ans + pre - a[i] + 1
		pre = pre + 1
	else:
		pre = a[i]
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
res = 0
last_upd = 0
for i in range(1, n):
	if a[i] <= a[i - 1]:
		res += a[i - 1] + 1 - a[i]
		a[i] = a[i - 1] + 1
print(res)


i = int(input())
v = sorted(list(map(int, input().split())))
cv = 0
tc = 0
for value in range(0, i):
	test = v[value]
	e = 0
	while e == 0:
		if test <= cv:
			tc += 1
			test += 1
		else:
			cv = test
			e = 1
print(tc)


n = int(input())
a = list(map(int, input().split()))
a.sort()
cnt = 0
p = 1
for i in range(n):
	if a[i] > p:
		n += a[i] - p
		p += a[i] - p
	elif a[i] != p:
		cnt += p - a[i]
	p += 1
print(cnt)


n = int(input())
l = [int(x) for x in input().split()]
kul = []
penz = 0
for i in range(n):
	nincsvege = True
	while nincsvege:
		if l[i] in kul:
			l[i] += 1
			penz += 1
		else:
			kul.append(l[i])
			nincsvege = False
print(penz)


size = int(input())
soldier = sorted(map(int, input().split()))
(occurrences, coins) = ({}, 0)
for s in soldier:
	if s not in occurrences:
		occurrences.update({s: 0})
	else:
		diff = s
		while diff in occurrences:
			diff += 1
		coins += diff - s
		occurrences.update({diff: 0})
print(coins)


n = int(input())
xs = sorted(map(int, input().split()))
r = 0
p = 0
for x in xs:
	if x <= p:
		d = p - x + 1
		r += d
		p = x + d
	else:
		p = x
print(r)


n = int(input())
nums = [int(num) for num in input().split()]
nums.sort()
in_sum = sum(nums)
for i in range(1, len(nums)):
	if nums[i] <= nums[i - 1]:
		nums[i] = nums[i - 1] + 1
print(sum(nums) - in_sum)


amount = int(input())
lst = input().split()
lst = [int(l) for l in lst]
lst.sort()
result = 0
last = lst[0]
for l in lst[1:]:
	if l <= last:
		result += last - l + 1
		last += 1
	else:
		last = l
print(result)


def p1():
	n = int(input())
	l = [int(i) for i in input().split()]
	l.sort()
	t = 0
	for i in range(1, n):
		if l[i] <= l[i - 1]:
			t += l[i - 1] - l[i] + 1
			l[i] = l[i - 1] + 1
	print(t)
p1()


n = int(input())
a = [int(x) for x in input().split()]
r = 0
d = set()
for x in a:
	while x in d:
		x += 1
		r += 1
	d.add(x)
print(r)


n = int(input())
a = list(map(int, input().split()))
a.sort()
p = 0
s = 0
for j in a:
	p += max(0, s + 1 - j)
	s = max(s + 1, j)
print(p)


n = int(input())
line = str(input()).split()
line = [int(it) for it in line]
line.sort()
candidate = 0
over_line = list()
for i in range(len(line)):
	candidate = max(candidate + 1, line[i])
	over_line.append(candidate)
print(sum(over_line) - sum(line))


n = int(input())
badges = [int(x) for x in input().split()]
badges.sort()
coin = 0
for i in range(len(badges) - 1):
	if badges[i] >= badges[i + 1]:
		coin += badges[i] - badges[i + 1] + 1
		badges[i + 1] = 1 + badges[i]
print(coin)


n = int(input())
L = list(map(int, input().split()))
L.sort()
r = 0
t = L[0]
for i in range(1, n):
	if L[i] <= t:
		r += 1 + t - L[i]
		t += 1
	else:
		t = L[i]
print(r)


n = int(input())
a = input().split()
a = [int(i) for i in a]
a.sort()
s = []
f = []
for i in range(3001):
	f.append(False)
for i in range(n):
	f[a[i]] = True
for i in range(3001):
	if f[i] == False:
		s.append(i)
for i in range(3005):
	s.append(i + 3001)
ans = 0
k = 0
for i in range(1, n):
	if a[i] == a[i - 1]:
		while s[k] < a[i]:
			k += 1
		ans += s[k] - a[i]
		k += 1
print(ans)


n = int(input())
a = sorted(list(map(int, input().split())))
i = 0
m = 0
while i < n - 1:
	if a[i] >= a[i + 1]:
		m += a[i] - a[i + 1] + 1
		a[i + 1] += a[i] - a[i + 1] + 1
	i += 1
print(m)


N = int(input())
A = sorted(list([int(x) - 1 for x in input().split()]))
A = list([x - A[0] for x in A])
bucket = [0] * 6010
for a in A:
	bucket[a] += 1
ans = 0
for i in range(6000):
	if bucket[i] > 1:
		ans += bucket[i] - 1
		bucket[i + 1] += bucket[i] - 1
print(ans)


n = int(input())
a = list(map(int, input().strip().split(' ')))
x = [0 for __ in range(7655)]
for i in a:
	x[i] += 1
a.sort()
ans = 0
for i in range(n):
	if x[a[i]] > 1:
		x[a[i]] -= 1
		for j in range(a[i], len(x)):
			if x[j] == 0:
				x[j] = 1
				ans += j - a[i]
				break
print(ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
c = 0
lst = sorted(list(map(int, input().split())))
for (i, j) in enumerate(lst):
	a = j
	lst[i] = -1
	while True:
		if a in lst:
			a = a + 1
			c = c + 1
		else:
			lst[i] = a
			break
print(c)


soliderCount = int(input())
signs = [int(sign) for sign in input().split(' ')]
signs.sort()
total = 0
real = signs[0]
reals = [real]
for sign in signs[1:]:
	if sign > real:
		real = sign
	else:
		real += 1
	reals.append(real)
print(sum(reals) - sum(signs))


from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
(b, c) = ([], [])
ans = 0
for i in a:
	j = i
	while bisect_left(c, j) < len(c):
		j += 1
	ans += j - i
	c.append(j)
print(ans)


n = input()
n = int(n)
badges = input()
badges = badges.split()
badges = [int(b) for b in badges]
badges.sort()
total_cost = 0
alternatives = [False for i in range(2 * n)]
badge = badges[0]
for i in range(n):
	if badge < badges[i]:
		badge = badges[i]
	if alternatives[badge] == False:
		alternatives[badge] = True
		total_cost += abs(badge - badges[i])
		badge += 1
print(total_cost)


def solve():
	ans = 0
	n = int(input())
	lst = list(map(int, input().split()))
	x = [0 for i in range(2 * n + 2)]
	for i in range(n):
		x[lst[i]] += 1
	cur = 0
	for i in range(1, 2 * n + 1):
		x[i] += cur
		if x[i] > 1:
			cur = x[i] - 1
			ans += x[i] - 1
			x[i] -= cur
		else:
			cur = 0
	print(ans)
solve()


import sys

def fastio():
	from io import StringIO
	from atexit import register
	global input
	sys.stdin = StringIO(sys.stdin.read())
	input = lambda : sys.stdin.readline().rstrip('\r\n')
	sys.stdout = StringIO()
	register(lambda : sys.__stdout__.write(sys.stdout.getvalue()))
fastio()

def debug(*var, sep=' ', end='\n'):
	print(*var, file=sys.stderr, end=end, sep=sep)
INF = 10 ** 20
MOD = 10 ** 9 + 7
I = lambda : list(map(int, input().split()))
from math import gcd
from math import ceil
from collections import defaultdict as dd, Counter
from bisect import bisect_left as bl, bisect_right as br
(n,) = I()
a = I()
d = [0] * 7000
for i in a:
	d[i] += 1
ans = 0
for i in range(7000):
	if d[i] > 1:
		ans += d[i] - 1
		d[i + 1] += d[i] - 1
print(ans)


number_of_icons = int(input())
soldiers = [int(i) for i in input().split()]
soldiers.sort()
result = 0
for i in range(len(soldiers)):
	for j in range(i + 1, len(soldiers)):
		if soldiers[i] == soldiers[j]:
			soldiers[j] += 1
			result += 1
		else:
			break
print(result)


n = int(input())
l1 = [int(i) for i in input().split()]
l1.sort()
num1 = 0
sum1 = 0
while num1 < n - 1:
	while l1[num1 + 1] <= l1[num1]:
		l1[num1 + 1] += 1
		sum1 += 1
	num1 += 1
print(sum1)


(s, k) = (0, 0)
input()
for i in sorted(map(int, input().split())):
	if i < k:
		s += k - i
		k += 1
	else:
		k = i + 1
print(s)


n = int(input())
u = []
s = [int(i) for i in input().split()]
s.sort()
s.append(6001)
n += 1
k = 0
for i in range(n - 1):
	if s[i] == s[i + 1]:
		u.append(i)
	elif u and s[i] + 1 < s[i + 1]:
		t = s[i] + 1
		while t < s[i + 1] and u:
			k += t - s[u.pop(0)]
			t += 1
print(k)


n = int(input())
a = list(map(int, input().split(' ')))
d = [0] * n
for item in a:
	d[item - 1] += 1
result = 0
for i in range(n - 1):
	dm1 = d[i] - 1
	if dm1 < 0:
		continue
	d[i + 1] += dm1
	result += dm1
result += d[n - 1] * (d[n - 1] - 1) // 2
print(result)


n = int(input())
a = list(map(int, input().split()))
a.sort()
s = set()
i = 0
ans = 0
while i < n:
	if a[i] in s:
		a[i] += 1
		ans += 1
	else:
		s.add(a[i])
		i += 1
print(ans)


n = int(input())
a = [int(i) for i in input().split()]
els = [0] * (2 * n)
for i in a:
	els[i - 1] += 1
ans = 0
for i in range(2 * n):
	if els[i] == 0:
		continue
	while els[i] != 1:
		els[i + 1] += 1
		els[i] -= 1
		ans += 1
print(ans)


n = int(input())
ans = 0
a = [int(_) for _ in input().split()]
a.sort()
for i in range(0, n):
	for j in range(i + 1, n):
		if a[j] == a[i]:
			a[j] += 1
			ans += 1
print(ans)


def main():
	n = int(input())
	s = input().split()
	for i in range(n):
		s[i] = int(s[i])
	s.sort()
	coin = 0
	for i in range(n - 1):
		if s[i] == s[i + 1] or s[i] > s[i + 1]:
			dif = abs(s[i + 1] - s[i])
			s[i + 1] += dif + 1
			coin += 1 + dif
	print(coin)
main()


a = int(input())
b = sorted(map(int, input().split()))
s = 0
for i in range(1, a):
	if b[i - 1] >= b[i]:
		r = b[i - 1] - b[i] + 1
		s += r
		b[i] = b[i - 1] + 1
print(s)


n = int(input())
a = sorted(list(map(int, input().split())))
cnt = 0
i = 0
while i < n - 1:
	while a[i] >= a[i + 1]:
		a[i + 1] += 1
		cnt += 1
	i += 1
print(cnt)


n = int(input())
l = sorted(map(int, input().split()))[::-1]
ans = 0
while len(set(l)) != n:
	for i in range(n - 1):
		if l[i] == l[i + 1]:
			l[i] += 1
			ans += 1
print(ans)


def solve(n, ll):
	nums = [0] * 6001
	dup = []
	for i in ll:
		if nums[i] == 1:
			dup.append(i)
		else:
			nums[i] = 1
	dup.sort()
	coins = 0
	for i in dup:
		right = i + 1
		while right < 6001:
			if nums[right] == 0:
				coins += abs(i - right)
				nums[right] = 1
				break
			right += 1
	return coins
n = int(input())
ll = list(map(int, input().split()))
print(solve(n, ll))


from collections import defaultdict
N = input()
a = input().split(' ')
a = map(int, a)
counts = defaultdict(int)
for e in a:
	counts[e] += 1
cost = 0
cont = True
while cont:
	cont = False
	for e in counts:
		if counts[e] > 1:
			counts[e + 1] += counts[e] - 1
			cost += counts[e] - 1
			counts[e] = 1
			cont = True
			break
print(cost)


n = int(input())
a = [int(x) for x in input().split()]
k = 0
m = set()
for x in a:
	while x in m:
		x += 1
		k += 1
	m.add(x)
print(k)


import atexit
import io
import sys
_I_B = sys.stdin.read().splitlines()
input = iter(_I_B).__next__
_O_B = io.StringIO()
sys.stdout = _O_B

@atexit.register
def write():
	sys.__stdout__.write(_O_B.getvalue())

def main():
	n = int(input())
	a = list(map(int, input().split()))
	d = dict()
	for i in range(1, 2 * n + 1):
		d[i] = 0
	for i in a:
		d[i] += 1
	cost = 0
	for i in d:
		while d[i] > 1:
			for j in range(i + 1, 2 * n + 1):
				if d[j] == 0:
					cost += j - i
					d[j] += 1
					break
			d[i] -= 1
	print(cost)
main()


n = int(input())
spisok = input().split()
spisok = list(spisok)
for i in range(n):
	spisok[i] = int(spisok[i])
spisok.sort()
answer = 0
for i in range(1, n):
	per = spisok[i - 1] + 1 - spisok[i] if spisok[i - 1] + 1 - spisok[i] > 0 else 0
	answer += per
	spisok[i] = spisok[i] + per if per > 0 else spisok[i]
print(answer)


def ii():
	return int(input())

def im():
	return map(int, input().split(' '))
n = ii()
res = 0
t = sorted(im())
i = 0
while i < n - 1:
	i += 1
	if t[i] <= t[i - 1]:
		res += 1
		t[i] += 1
		i -= 1
print(res)


from sys import stdin, stdout
n = int(stdin.readline())
arr = list(map(int, stdin.readline().split()))
length = 10000
ans = [0 for i in range(length)]
for i in range(len(arr)):
	ans[arr[i]] += 1
change = 0
j = 0
for i in range(length):
	if ans[i] > 1:
		j = i
		pick = ans[i] - 1
		while pick > 0:
			if ans[j] == 0:
				ans[j] = 1
				pick -= 1
				change += j - i
			j += 1
		ans[i] = 1
stdout.write(str(change) + '\n')


n = int(input())
badges = list(map(int, input().split()))
counter = [0 for i in range(6005)]
for b in badges:
	counter[b] += 1
cost = 0
for i in range(len(counter)):
	if counter[i] > 1:
		for j in range(i + 1, len(counter)):
			if counter[j] == 0:
				counter[j] = counter[i] - 1
				cost += (counter[i] - 1) * (j - i)
				counter[i] = 1
print(cost)


number = int(input())
badge_list = list(map(int, input().split()))
badge_list.sort()
cost = 0
for i in range(number - 1):
	if badge_list[i + 1] <= badge_list[i]:
		cost += badge_list[i] + 1 - badge_list[i + 1]
		badge_list[i + 1] = badge_list[i] + 1
print(cost)


def solve(arr):
	arr.sort()
	count = 0
	s = set()
	for i in range(len(arr)):
		if arr[i] not in s:
			s.add(arr[i])
		else:
			no = arr[i]
			while no in s:
				no += 1
				count += 1
			arr[i] = no
			s.add(no)
	return count
n = int(input())
arr = list(map(int, input().split()))
print(solve(arr))


def solve(n, seq):
	refer = [0] * 10000
	ans = 0
	for x in seq:
		refer[x] = 1
	index = 0
	index2 = 0
	while index < n - 1:
		index2 = index + 1
		while index2 < n:
			if seq[index] == seq[index2]:
				tar = seq[index]
				while refer[tar] == 1:
					ans += 1
					tar += 1
				refer[tar] = 1
				seq[index2] = tar
			index2 += 1
		index += 1
	return ans
n = int(input())
seq = list(map(int, input().split()))
print(solve(n, seq))


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
z = []
res = 0
for i in range(0, n - 1):
	while a[i + 1] <= a[i]:
		a[i + 1] += 1
		res += 1
print(res)


n = int(input())
l = list(map(int, input().split()))
l.sort()
s = set()
c = 0
for i in range(n):
	if l[i] not in s:
		s.add(l[i])
	else:
		var = l[i]
		while var in s:
			var += 1
			c += 1
		s.add(var)
print(c)


n = int(input())
li = [int(c) for c in input().split()]
li.sort()
m = 0
for i in range(1, n):
	if li[i] <= li[i - 1]:
		m += li[i - 1] - li[i] + 1
		li[i] = li[i - 1] + 1
print(m)


n = int(input())
l = [int(i) for i in input().split()]
l.sort()
res = 0
for i in range(1, n):
	if l[i] <= l[i - 1]:
		res += l[i - 1] - l[i] + 1
		l[i] += l[i - 1] - l[i] + 1
print(res)


n = int(input())
a = [int(i) for i in input().split()]
a = sorted(a)
coin = 0
for i in range(1, len(a)):
	if a[i] > a[i - 1]:
		continue
	coin += a[i - 1] - a[i] + 1
	a[i] += a[i - 1] - a[i] + 1
print(coin)


n = int(input())
a = input().strip().split()
for (index, item) in enumerate(a):
	a[index] = int(item)
a.sort()
ans = 0
for i in range(1, n):
	if a[i] <= a[i - 1]:
		ans += a[i - 1] + 1 - a[i]
		a[i] = a[i - 1] + 1
print(ans)


from sys import stdin as sin

def aint():
	return int(input())

def amap():
	return map(int, sin.readline().split())

def alist():
	return list(map(int, sin.readline().split()))

def astr():
	return input()
n = aint()
l = alist()
ans = 0
g = set()
for i in range(n):
	j = 0
	while j + l[i] in g:
		j += 1
		ans += 1
	g.add(j + l[i])
print(ans)


n = int(input())
words = input().split()
nums = []
for word in words:
	nums.append(int(word))
nums.sort()
inc = 0
for i in range(n - 1):
	m = nums[i]
	if not nums[i + 1] > m:
		inc += m + 1 - nums[i + 1]
		nums[i + 1] = m + 1
print(inc)


count = 0
n = input()
n = int(n)
b = [int(i) for i in input().split(' ')]
b = sorted(b)
for i in range(1, n):
	if b[i] == b[i - 1]:
		b[i] = b[i] + 1
		count = count + 1
	elif b[i] < b[i - 1]:
		diff = b[i - 1] - b[i]
		b[i] = b[i] + diff + 1
		count = count + diff + 1
print(count)


def znachki(lst):
	count = 0
	for i in range(1, len(lst)):
		if lst[i] > lst[i - 1]:
			continue
		count += lst[i - 1] - lst[i] + 1
		lst[i] = lst[i - 1] + 1
	return count
n = int(input())
a = [int(j) for j in input().split()]
print(znachki(sorted(a)))


n = int(input())
ls = [int(a) for a in input().split()]
ls.sort()
ls1 = [0] * 2 * n
for i in range(n):
	ls1[ls[i] - 1] += 1
sm = 0
i = 0
while i < n:
	if ls1[i] > 1:
		idx = ls1.index(0)
		sm += idx - i
		ls1[idx] += 1
		ls1[i] -= 1
		i -= 1
	else:
		ls1[i] = 1
	i += 1
print(sm)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def pf(s):
	return print(s, flush=True)

def main():
	n = I()
	a = sorted(LI())
	t = -1
	r = 0
	for c in a:
		if t >= c:
			r += t - c + 1
			t = t + 1
		else:
			t = c
	return r
print(main())


n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
k = 0
for i in range(n):
	l1 = 1
	for j in range(n):
		if i != j and l[i] == l[j]:
			l[j] = l[i] + l1
			k = k + l1
			l1 = l1 + 1
print(k)


n = int(input())
a = list(map(int, input().split(' ')))
a.sort()
result = 0
for i in range(1, n):
	while a[i] <= a[i - 1]:
		a[i] += 1
		result += 1
print(result)


n = int(input())
bagdes = list(map(int, input().split()))
bagdes.sort()
res = 0
for i in range(n - 1):
	if bagdes[i + 1] <= bagdes[i]:
		res = res + (bagdes[i] - bagdes[i + 1] + 1)
		bagdes[i + 1] = bagdes[i] + 1
print(res)


n = int(input())
l = list(map(int, input().strip().split()))
d = {}
arr = []
for i in l:
	try:
		d[i] += 1
	except KeyError:
		d[i] = 1
		arr.append(i)
arr.sort()
curr = arr[0] - 1
ans = 0
for j in arr:
	if curr < j:
		m = d[j]
		ans += m * (m - 1) // 2
		curr = j + m - 1
	else:
		m = d[j]
		pay = curr + 1 - j
		ans += pay * m + m * (m - 1) // 2
		curr = curr + m
print(ans)


n = int(input())
a = input()
a = a.split()
for x in range(n):
	a[x] = int(a[x])
count = 0
a = sorted(a)
p = 0
flag = a[p] + 1
for x in range(n - 1):
	temp = flag - a[x + 1]
	if temp >= 0:
		count += temp
	else:
		p = x + 1
		flag = a[p]
	flag += 1
print(count)


import sys

def main():
	n = int(input())
	a = sorted([int(i) for i in input().split()])
	ans = 0
	for i in range(n):
		for j in range(n):
			if i != j and a[i] == a[j]:
				a[j] += 1
				ans += 1
	print(ans)
main()


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
vis = [0 for i in range(10000)]
ans = 0
for i in arr:
	if vis[i] == 0:
		vis[i] = 1
	else:
		for j in range(i + 1, 10000):
			if vis[j] == 0:
				vis[j] = 1
				ans += abs(i - j)
				c = j
				break
print(ans)


def main():
	n = int(eval(input()))
	ls = [int(k) for k in input().split()]
	ls = sorted(ls)
	cost = sum(ls)
	for i in range(1, n):
		if ls[i] <= ls[i - 1]:
			ls[i] = ls[i - 1] + 1
	print(sum(ls) - cost)
main()


n = int(input())
a = list(map(int, input().split()))
mi = min(a)
sum = 0
b = []
k = []
for i in set(a):
	if a.count(i) > 1:
		for j in range(a.count(i) - 1):
			b.append(i)
b.sort()
for i in range(mi, n + 1):
	if i not in a:
		k.append(i)
for i in range(n + 1, 2 * n + 2):
	k.append(i)
while len(b) != 0:
	if b[0] < k[0]:
		sum += k[0] - b[0]
		del b[0]
		del k[0]
	else:
		del k[0]
print(sum)


n = int(input())
l1 = list(map(int, input().split()))
l2 = [0] * int(n * (n + 1) / 2)
cost = 0
for i in range(n):
	if l2[l1[i] - 1] == 0:
		l2[l1[i] - 1] = 1
	elif l2[l1[i] - 1] == 1:
		while l2[l1[i] - 1] == 1:
			cost += 1
			l1[i] += 1
		l2[l1[i] - 1] = 1
print(cost)


n = int(input().strip())
lll = list(map(int, input().split()))
ll1 = [0] * 6051
for i in range(n):
	ll1[lll[i]] += 1
otvet = 0
jjjj = []
for i in range(1, 6051):
	if ll1[i] > 1:
		for j in range(ll1[i] - 1):
			jjjj.append(i)
	elif ll1[i] == 0 and len(jjjj) != 0:
		otvet += i - jjjj[0]
		jjjj = jjjj[1:]
print(otvet)


n = int(input().strip())
arr = list(map(int, input().strip().split()))
arr.sort()
taken = set()
for i in arr:
	taken.add(i)
c = 0
i = 1
while i < n:
	if arr[i] == arr[i - 1]:
		replacement = arr[i] + 1
		while True:
			if replacement in taken:
				replacement += 1
			else:
				break
		c += replacement - arr[i]
		arr[i] = replacement
		taken.add(replacement)
		arr.sort()
	else:
		i += 1
print(c)


n = int(input())
arr = list(map(int, input().split()))
arr.sort()
p = 0
s = 0
for x in arr:
	s += max(0, p - x + 1)
	p = max(p + 1, x)
print(s)


import math, sys
from collections import defaultdict, Counter, deque
INF = float('inf')
MOD = 1000000007

def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a

def isPrime(n):
	if n <= 1:
		return False
	i = 2
	while i ** 2 <= n:
		if n % i == 0:
			return False
		i += 1
	return True

def primeFactors(n):
	factors = []
	i = 2
	while i ** 2 <= n:
		while n % i == 0:
			factors.append(i)
			n //= i
		i += 1
	if n > 1:
		factors.append(n)
	return factors

def vars():
	return map(int, input().split())

def array():
	return list(map(int, input().split()))

def main():
	n = int(input())
	arr = array()
	arr.sort()
	cnt = 0
	for i in range(1, n):
		if arr[i] <= arr[i - 1]:
			cnt += arr[i - 1] + 1 - arr[i]
			arr[i] = arr[i - 1] + 1
	print(cnt)
t = 1
for _ in range(t):
	main()


n = int(input())
l = [int(x) for x in input().split()]
s = set()
ans = 0
for x in l:
	while x in s:
		ans += 1
		x += 1
	s.add(x)
print(ans)


input()
p = v = 0
for i in sorted(map(int, input().split())):
	v += max(0, p - i + 1)
	p = max(p + 1, i)
print(v)


import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
n = int(input())
a = [int(i) for i in input().split()]
cnt = [0] * (2 * n + 10)
rem = 0
ans = 0
for i in a:
	cnt[i] += 1
for i in range(len(cnt)):
	ans += rem
	if cnt[i] > 1:
		rem += cnt[i] - 1
	elif cnt[i] == 0:
		rem = max(rem - 1, 0)
print(ans)


input()
ans = 0
a = sorted(map(int, input().split()))
prev = 0
for i in a:
	if i <= prev:
		ans += prev - i + 1
		prev = prev + 1
	else:
		prev = i
print(ans)


n = int(input())
array = [0] * n
array = input().split()
for i in range(n):
	array[i] = int(array[i])
array.sort()
answer = 0
for i in range(1, n):
	if array[i] <= array[i - 1]:
		answer += array[i - 1] - array[i] + 1
		array[i] = array[i - 1] + 1
print(answer)


n = int(input())
arr = sorted(list(map(int, input().split())))
(t, res) = (-1, 0)
for i in arr:
	if t >= i:
		res += t - i + 1
		t = t + 1
	else:
		t = i
print(res)


n = int(input())
l = list(map(int, input().split(' ')))
l.sort()
counter = 0
for i in range(1, len(l)):
	if l[i] == l[i - 1]:
		l[i] += 1
		counter += 1
	elif l[i] < l[i - 1]:
		buff = l[i - 1] - l[i]
		l[i] = l[i] + buff + 1
		counter = counter + buff + 1
print(counter)


n = int(input())
a = sorted(list(map(int, input().split())))
(cnt, M) = (0, a[0])
for i in range(1, n):
	if a[i] <= M:
		cnt += M - a[i] + 1
		M += 1
	else:
		M = a[i]
print(cnt)


n = int(input())
a = sorted(map(int, input().split()))
(s, b) = (set(), [])
for i in range(len(a)):
	if a[i] in s:
		b.append(a[i])
	else:
		s.add(a[i])
for i in b:
	while i in s:
		i += 1
	s.add(i)
print(sum(s) - sum(a))


trash = [int(n) for n in input().split()]
a = [int(n) for n in input().split()]
a.sort()
cost = 0
for i in range(len(a) - 1, 0, -1):
	if a[i] == a[i - 1]:
		for j in range(i + 1, len(a) + 1):
			if j == len(a) or a[j] - a[j - 1] > 1:
				cost += a[j - 1] + 1 - a[i]
				a.insert(j, a[j - 1] + 1)
				trash = a.pop(i)
				break
print(cost)


N = int(input())
X = sorted(list(map(int, input().split(' '))))
M = []
S = 0
for I in X:
	J = I
	while True:
		if J in M:
			J += 1
		else:
			M.append(J)
			S += J - I
			break
print(S)


n = int(input())
factor = list(map(lambda x: int(x), input().split()))

def mergeSort(arr):
	if len(arr) > 1:
		mid = len(arr) // 2
		L = arr[:mid]
		R = arr[mid:]
		mergeSort(L)
		mergeSort(R)
		i = j = k = 0
		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1
		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1
mergeSort(factor)
coin = 0
for i in range(n):
	while factor[i] in factor[:i]:
		factor[i] += 1
		coin += 1
print(coin)


n = int(input())
a = list(map(int, input().split()))
num = [0] * 10001
for i in a:
	num[i] += 1
res = 0
for i in range(1, 10001):
	if num[i] > 1:
		res += num[i] - 1
		num[i + 1] += num[i] - 1
print(res)


import sys

def main():
	sys.stdin.readline()
	badges = map(int, sys.stdin.readline().split())
	price = 0
	existing_badges = set()
	for b in sorted(badges):
		while b in existing_badges:
			price += 1
			b += 1
		existing_badges.add(b)
	print(price)

def __starting_point():
	main()
__starting_point()


a = int(input())
b = sorted(list(map(int, input().split())))
(ctr, tot) = (1, 0)
while ctr < a:
	while b[ctr] <= b[ctr - 1]:
		b[ctr] += 1
		tot += 1
	ctr += 1
print(tot)


a = int(input())
t = list(map(int, input().split()))
x = sum(t)
u = 0
if a == 1:
	print(0)
else:
	t.sort()
	for k in range(1, a):
		if t[k] > t[k - 1]:
			pass
		else:
			t[k] = t[k - 1] + 1
	print(sum(t) - x)


n = int(input())
a = sorted(map(int, input().split()))
p = sum(a)
for i in range(1, n):
	if a[i] <= a[i - 1]:
		a[i] = a[i - 1] + 1
print(sum(a) - p)


l = int(input())
a = [int(i) for i in input().strip().split()]
a = sorted(a)
i = 0
flag = False
cost = 0
while i < l:
	cur = a[i]
	i += 1
	if i >= l:
		break
	if a[i] == cur:
		a[i] += 1
		cost += 1
	if a[i] < cur:
		cost += cur - a[i] + 1
		a[i] += cur - a[i] + 1
	else:
		continue
print(cost)


n = int(input())
a = list(map(int, input().split()))
a.sort()
d = {}
ans = 0
i = 0
while len(d) != n:
	if a[i] not in d:
		d[a[i]] = 1
		i += 1
	else:
		while a[i] in d:
			ans += 1
			a[i] += 1
		d[a[i]] = 1
		i += 1
print(ans)


import sys
R = lambda : list(map(int, input().split()))
n = R()[0]
a = R()
a.sort()
ans = 0
vis = [False for i in range(2 * n + 10)]
for x in a:
	vis[x] = True
for i in range(n):
	if i != 0 and a[i] == a[i - 1]:
		for j in range(a[i] + 1, 2 * n + 4):
			if vis[j] is False:
				vis[j] = True
				ans += j - a[i]
				break
print(ans)


n = int(input())
l = list(map(int, input().split()))

def sort(a):
	l = len(a)
	for i in range(l - 1):
		for j in range(l - 1 - i):
			if a[j] > a[j + 1]:
				(a[j], a[j + 1]) = (a[j + 1], a[j])
sort(l)
t = 0
t2 = 0
r = 0
for i in range(n):
	while l[i] + t2 <= t:
		t2 += 1
	r += t2
	l[i] = l[i] + t2
	t = l[i]
	t2 = 0
print(r)


input()
l = sorted([int(i) for i in input().split()])
x = sum(l)
for i in range(1, len(l)):
	if l[i - 1] >= l[i]:
		l[i] = l[i - 1] + 1
print(sum(l) - x)


n = int(input())
badges = list(map(int, input().split()))
coolness = [0 for i in range(8000)]
max_badge = 0
ans = 0
for i in range(n):
	coolness[badges[i] - 1] += 1
	if badges[i] > max_badge:
		max_badge = badges[i]
for i in range(0, 7999):
	if coolness[i] > 1:
		ans += coolness[i] - 1
		coolness[i + 1] += coolness[i] - 1
print(ans)


n = int(input())
x = list(map(int, input().split()))
x.sort()
ans = 0
for i in range(1, n):
	if x[i] <= x[i - 1]:
		ans += abs(x[i] - x[i - 1]) + 1
		x[i] += abs(x[i] - x[i - 1]) + 1
print(ans)


n = int(input())
nums = list(map(int, input().split(' ')))
t = [0 for i in range(6002)]
ret = 0
for i in nums:
	t[i] += 1
ret = 0
for i in range(len(t)):
	if t[i] > 0:
		ret += t[i] - 1
		t[i + 1] += t[i] - 1
print(ret)


def main():
	n = int(input())
	badges = list(map(int, input().split()))
	badges.sort()
	cost = 0
	for i in range(n - 1):
		if badges[i + 1] <= badges[i]:
			cost += badges[i] + 1 - badges[i + 1]
			badges[i + 1] = badges[i] + 1
	print(cost)
main()


n = int(input())
cool = [int(i) for i in input().split()]
cool.sort()
total = 0
for i in range(n - 1):
	if cool[i + 1] <= cool[i]:
		total += cool[i] - cool[i + 1] + 1
		cool[i + 1] = cool[i] + 1
print(total)


n = int(input())
a = sorted(list(map(int, input().split())))
coins = temp = 0
for i in range(n):
	if temp >= a[i]:
		temp += 1
		coins += temp - a[i]
	else:
		temp = a[i]
print(coins)


n = int(input())
A = list(map(int, input().split()))
m = 2 * (n + 1)
B = [0 for i in range(m)]
for i in A:
	B[i] += 1
c = 0
for i in range(n):
	if B[A[i]] > 1:
		for j in range(A[i] + 1, m):
			c = c + 1
			if B[j] == 0:
				B[A[i]] -= 1
				A[i] = j
				B[A[i]] += 1
				break
print(c)


n = int(input())
data = [int(i) for i in input().split()]
data.sort()
c = 0
for i in range(1, n):
	if data[i] <= data[i - 1]:
		c += data[i - 1] - data[i] + 1
		data[i] = data[i - 1] + 1
print(c)


n = int(input())
l = list(map(int, input().split()))
l.sort()
hash = [0] * 6001
for i in range(n):
	hash[l[i]] = 1
transferable = []
for i in range(1, 6001):
	if hash[i] == 0:
		transferable.append(i)
for i in range(len(transferable)):
	if transferable[0] < l[0]:
		transferable.pop(0)
	else:
		break
repeated = []
for i in range(1, n):
	if l[i] == l[i - 1]:
		repeated.append(l[i])
ans = 0
j = 0
i = 0
while i < len(repeated):
	if transferable[j] <= repeated[i]:
		j += 1
	else:
		ans += transferable[j] - repeated[i]
		j += 1
		i += 1
print(ans)


n = int(input())
a = list(map(int, input().rstrip().split()))
li = []
c = 0
for x in a:
	if x not in li:
		li += [x]
	else:
		y = x + 1
		while True:
			if y not in li:
				li += [y]
				c += y - x
				break
			y += 1
print(c)


n = int(input())
a = input().split()
for i in range(n):
	a[i] = int(a[i])
a.sort()
k = 0
for i in range(1, n):
	while a[i] <= a[i - 1]:
		a[i] += 1
		k += 1
print(k)


n = int(input())
s = sorted(map(int, input().split()))
(c, t) = (s[0], 0)
for x in s:
	if x < c:
		c += 1
		t += c - x - 1
	elif x == c:
		c += 1
	elif x > c:
		c = x + 1
print(t)


N = int(input(''))
inputlist = [int(i) for i in input('').split()]
seen = set()
coins = 0
for i in inputlist:
	while i in seen:
		i += 1
		coins += 1
	seen.add(i)
print(coins)


n = int(input())
L = [int(s) for s in input().split()]
L.sort()
cost = 0
for i in range(len(L) - 1):
	while L[i] >= L[i + 1]:
		L[i + 1] += 1
		cost += 1
print(cost)


n = int(input())
a = list(map(int, input().split()))
b = {}
c = 0
for i in a:
	if i in b:
		while i in b:
			i = i + 1
			c = c + 1
		b[i] = 1
	else:
		b[i] = 1
print(c)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
cnt = 0
for i in range(n):
	for j in range(i + 1, n):
		if a[i] == a[j]:
			cnt += 1
			a[j] += 1
print(cnt)


n = int(input())
l = list(map(int, input().split()))
l.sort()
a = 0
count = 0
for i in range(len(l)):
	if a >= l[i]:
		count += a - l[i] + 1
		l[i] += a - l[i] + 1
		a += 1
	else:
		a = l[i]
print(count)


import sys
fast_reader = sys.stdin.readline
fast_writer = sys.stdout.write

def input():
	return fast_reader().strip()

def print(*argv):
	fast_writer(' '.join((str(i) for i in argv)))
	fast_writer('\n')
n = int(input())
l = list(map(int, input().split()))
l.sort()
s = set()
ans = 0
for i in range(n):
	if l[i] not in s:
		s.add(l[i])
	else:
		for j in range(l[i] + 1, 2 * n + 1):
			if j not in s:
				ans += j - l[i]
				s.add(j)
				break
print(ans)


n = int(input())
signs = sorted([int(i) for i in input().split()])
new_s = []
acc = 0
for i in signs:
	j = i
	if j in new_s:
		k = new_s.index(j)
		while k < len(new_s) and new_s[k] == j:
			acc += 1
			j += 1
			k += 1
	new_s.append(j)
	new_s = sorted(new_s)
print(acc)


input()
a = list(map(int, input().split()))
a.sort()
mx = 0
t = 0
for x in a:
	mx = max(mx + 1, x)
	t += mx
print(t - sum(a))


n = int(input())
a = list(map(int, input().split()))
a.sort()
(x, ans) = (0, 0)
for ii in a:
	if x >= ii:
		ans += x + 1 - ii
		x = x + 1
	else:
		x = ii
print(ans)


x = input()
x = list(map(int, input().split(' ')))
x.sort()
x.append(100000)
last = x[0]
acc = 0
cost = 0
for i in range(1, len(x)):
	if x[i] != last:
		c = 0
		while acc > 0:
			c += 1
			cost += acc
			acc -= 1
			last += 1
			if last == x[i] and c > 0:
				acc += 1
				break
		last = x[i]
	elif x[i] == last:
		acc += 1
print(acc + cost)


n = int(input())
l = list(map(int, input().split()))
l.sort()
s = sum(l)
for i in range(1, n):
	if l[i] <= l[i - 1]:
		l[i] = l[i - 1] + 1
print(sum(l) - s)


from sys import *
from bisect import bisect_left
input = lambda : stdin.readline()
int_arr = lambda : list(map(int, stdin.readline().strip().split()))
str_arr = lambda : list(map(str, stdin.readline().split()))
get_str = lambda : map(str, stdin.readline().strip().split())
get_int = lambda : map(int, stdin.readline().strip().split())
get_float = lambda : map(float, stdin.readline().strip().split())
mod = 1000000007
setrecursionlimit(1000)
n = int(input())
arr = int_arr()
lst = []
for i in range(1, 9000):
	if i not in arr:
		lst += [i]
arr.sort()
(ind, ct) = (0, 0)
for i in range(1, n):
	if arr[i - 1] == arr[i]:
		val = bisect_left(lst, arr[i])
		ct += abs(lst[val] - arr[i])
		lst[val] = -1
print(ct)


def main(n, a):
	ans = 0
	for i in range(1, n):
		if a[i] <= a[i - 1]:
			d = abs(a[i] - a[i - 1]) + 1
			ans += d
			a[i] += d
	return ans
print(main(int(input()), sorted(list(map(int, input().split(' '))))))


from bisect import bisect_left as bl

def main():
	n = int(input())
	a = sorted((int(c) for c in input().split()))
	aset = set(a)
	empty = [i for i in range(1, n + 1) if i not in aset]
	empty += list(range(n + 1, 3 * n))
	i = 0
	res = 0
	for i in range(len(a) - 1):
		if a[i + 1] == a[i]:
			l = bl(empty, a[i])
			r = l + 1
			dl = abs(empty[l] - a[i])
			dr = abs(empty[r] - a[i])
			if dl <= dr:
				del empty[l]
				res += dl
			else:
				del empty[r]
				res += dr
	print(res)
main()


import itertools as ittls
from collections import Counter
import string

def sqr(x):
	return x * x

def inputarray(func=int):
	return map(func, input().split())
N = int(input())
A = sorted(inputarray())
s = 0
for i in range(1, len(A)):
	while A[i] <= A[i - 1]:
		A[i] = A[i] + 1
		s = s + 1
print(s)


input()
(step, ans) = (0, 0)
mat = sorted(map(int, input().split()))
for i in mat:
	ans += max(0, step - i + 1)
	step = max(step + 1, i)
print(ans)


def arr_inp():
	return [int(x) for x in stdin.readline().split()]
from sys import stdin
(n, a, ans) = (int(input()), sorted(arr_inp()), 0)
for i in range(1, n):
	if a[i] <= a[i - 1]:
		ans += a[i - 1] - a[i] + 1
		a[i] += a[i - 1] - a[i] + 1
print(ans)


n = int(input())
arr = list(map(int, input().strip().split(' ')))
arr.sort()
res = 0
pre = arr[0]
for i in range(1, n):
	if arr[i] == pre:
		arr[i] += 1
		res += 1
		for j in range(i + 1, n):
			if arr[j] == pre:
				arr[j] += 1
				res += 1
			else:
				break
	pre = arr[i]
print(res)


n = int(input())
a = list(map(int, input().split()))
arr = [0 for _ in range(1, n + 2)]
for e in a:
	arr[e - 1] += 1
empty = set(range(1, n + 2)) - set(a)
mx = max(empty)
ans = 0
for (i, n) in enumerate(arr):
	for _ in range(n - 1):
		for e in empty:
			if e > i + 1:
				nxt = e
				break
		empty -= {nxt}
		if nxt == mx:
			mx += 1
			empty.add(mx)
		ans += nxt - i - 1
print(ans)


n = int(input())
badges = [int(x) for x in input().split()]
badges.sort()
coins = 0
for i in range(1, n):
	while badges[i] <= badges[i - 1]:
		coins += 1
		badges[i] += 1
print(coins)


n = int(input())
k = 0
if n == 1:
	print(0)
	exit()
a = list(map(int, input().split()))
b = []
c = []
for i in range(n * n):
	b.append(0)
for i in range(n):
	if b[a[i]] == 0:
		b[a[i]] = a[i]
	else:
		c.append(a[i])
for i in range(len(c)):
	for j in range(c[i], len(b)):
		if b[j] == 0:
			k += b[j - 1] - c[i] + 1
			b[j] = j
			break
print(k)


import os
import sys
from io import BytesIO, IOBase

def solution(arr, n):
	arr.sort()
	strict = arr[:]
	for i in range(1, n):
		if strict[i] <= strict[i - 1]:
			strict[i] = strict[i - 1] + 1
	res = sum((abs(strict[i] - arr[i]) for i in range(n)))
	write(res)

def main():
	n = r_int()
	arr = r_array()
	solution(arr, n)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')

def write(*args, end='\n'):
	for x in args:
		sys.stdout.write(str(x) + ' ')
	sys.stdout.write(end)

def r_array():
	return [int(x) for x in input().split()]

def r_int():
	return int(input())
main()


import math
import sys
n = int(input())
c = list(map(int, input().split()))
c.sort()
ans = 0
for i in range(1, n):
	if c[i] <= c[i - 1]:
		ans += c[i - 1] + 1 - c[i]
		c[i] = c[i - 1] + 1
print(ans)


n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for f in range(1, n):
	if l[f] <= l[f - 1]:
		ans += l[f - 1] - l[f] + 1
		l[f] = l[f - 1] + 1
print(ans)


n = int(input())
theBadges = input().split()
theBadges = [int(x) for x in theBadges]
theBadges.sort()
answer = 0
for i in range(n - 1):
	if theBadges[i] >= theBadges[i + 1]:
		answer = answer + theBadges[i] - theBadges[i + 1] + 1
		theBadges[i + 1] = theBadges[i] + 1
print(answer)


n = int(input())
c = list(map(int, input().split()))
c.sort()
l = 0
for i in range(1, n):
	if c[i] <= c[i - 1]:
		k = c[i - 1] - c[i] + 1
		c[i] += k
		l += k
print(l)


import collections
line = input()
if line:
	n = int(line)
	line = input()
	a = []
	for x in line.split():
		a.append(int(x))
		ans = 0
	counts = {}
	for kw in a:
		counts.setdefault(kw, 0)
		counts[kw] += 1
	for i in range(1, 10000):
		counts.setdefault(i, 0)
		counts.setdefault(i + 1, 0)
		if counts[i] > 1:
			counts[i + 1] += counts[i] - 1
			ans += counts[i] - 1
	print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
ans = 0
for i in range(1, n):
	if A[i] <= A[i - 1]:
		ans += A[i - 1] - A[i] + 1
		A[i] = A[i - 1] + 1
print(ans)


n = int(input())
cool_factors = [int(item) for item in input().strip().split(' ')]
cool_factors.sort()
acc = 0
for i in range(1, len(cool_factors)):
	if cool_factors[i] <= cool_factors[i - 1]:
		diff = cool_factors[i - 1] - cool_factors[i] + 1
		cool_factors[i] = cool_factors[i - 1] + 1
		acc += diff
print(acc)


n = int(input())
ls = sorted(list(map(int, input().split())))
ans = 0
for i in range(1, n):
	if ls[i] > ls[i - 1]:
		continue
	tmp = ls[i]
	ls[i] = ls[i - 1] + 1
	ans += ls[i] - tmp
print(ans)


test_case = int(input())
lim = input().split()
array = [0 for x in range(7000)]
count = 0
ans = 0
for i in range(0, test_case):
	array[int(lim[i])] += 1
fact = 1
while count < test_case:
	if array[fact] >= 1:
		array[fact + 1] += array[fact] - 1
		ans += array[fact] - 1
		count += 1
	fact += 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
d = []
for i in range(1, n):
	if a[i] == a[i - 1]:
		d += [a[i]]
av = []
for i in range(a[0], a[0] + n + n):
	if i not in a:
		av += [i]
sm = 0
i = 0
j = 0
while i < len(d):
	if av[j] >= d[i]:
		res = av[j] - d[i]
		sm += res
		j += 1
		i += 1
	else:
		j += 1
print(sm)


n = int(input())

def inp(s):
	j = 0
	a = []
	for i in range(len(s)):
		if s[i] == ' ':
			a.append(int(s[j:i]))
			j = i + 1
		if i == len(s) - 1:
			a.append(int(s[j:]))
	return sorted(a)
s = input()
a = inp(s)
r = 0
j = 0
for i in range(len(a)):
	if a.count(a[i]) > 1:
		if a[i] > j:
			j = a[i]
		while j in a:
			j = j + 1
		r = r + j - a[i]
		a[i] = j
print(r)


import math
import collections
import bisect
import heapq
import time
import random
import itertools
import sys
N = int(input())
A = [int(x) for x in input().split()]
V = [0] * (N * 2 + 1)
ans = 0
for v in sorted(A):
	if V[v] == 0:
		V[v] = 1
	else:
		for i in range(v + 1, N * 2 + 1):
			if V[i] == 0:
				V[i] = 1
				ans += i - v
				break
print(ans)


(n, coins_needed, badges_used) = (int(input()), 0, set())
for badge in [int(i) for i in input().split()]:
	if badge not in badges_used:
		badges_used.add(badge)
	else:
		while True:
			badge += 1
			coins_needed += 1
			if badge not in badges_used:
				badges_used.add(badge)
				break
print(coins_needed)


n = int(input())
a = list(map(int, input().split()))
m = n * 2 + 2
c = [0] * m
for i in range(n):
	c[a[i]] += 1
co = 0
for i in range(1, m):
	if c[i] > 1:
		x = c[i] - 1
		co += x
		c[i + 1] += x
print(co)


import sys
import math as mt
input = sys.stdin.buffer.readline
t = 1
for __ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	d = {}
	occ = [0] * 7000
	for i in range(n):
		occ[l[i]] = 1
		d[l[i]] = d.get(l[i], 0) + 1
	ans = 0
	l = list(set(l))
	l.sort(reverse=True)
	n = len(l)
	for i in range(n):
		for j in range(d[l[i]] - 1):
			k = l[i]
			for j1 in range(k + 1, 7000):
				ans += 1
				if occ[j1] == 0:
					occ[j1] = 1
					break
	print(ans)


n = input()
badges = [int(x) for x in input().split()]
dict = {}
cost = 0
for item in badges:
	while 1:
		try:
			dict[item] += 0
			item += 1
			cost += 1
		except:
			dict[item] = 1
			break
print(cost)


n = int(input())
an = list(map(int, input().split()))
arr = [0] * 3002
for i in an:
	arr[i - 1] += 1
res = 0
for i in range(0, 3001):
	if arr[i] > 1:
		res += arr[i] - 1
		arr[i + 1] += arr[i] - 1
if arr[3001] > 1:
	res += int(arr[3001] * (arr[3001] - 1) / 2)
print(res)


z = None

def nxt(b, n):
	if b >= n:
		return b
	i = b
	while i < n and z[i] == True:
		i += 1
	return i

def solve():
	n = int(input())
	s = input()
	a = [int(x) - 1 for x in s.split()]
	if n == 1:
		print(0)
		return
	a = sorted(a)
	global z
	z = [False for x in a]
	for x in a:
		z[x] = True
	(ans, bgn) = (0, 0)
	for (i, x) in enumerate(a[1:]):
		if x == a[i]:
			bgn = max(bgn, x + 1)
			bgn = nxt(bgn, n)
			ans += bgn - x
			bgn += 1
	print(ans)
solve()


n = int(input())
arr = sorted(list(map(int, input().split())))
d = []
repeated = []
x = arr[0]
for i in range(1, len(arr)):
	if x == arr[i]:
		repeated.append(x)
	elif arr[i] - x >= 1:
		while x < arr[i] - 1:
			d.append(x + 1)
			x = x + 1
		x = x + 1
ans = 0
if repeated == []:
	print(0)
	exit()
for i in repeated:
	if d != []:
		for j in range(len(d)):
			if i < d[j]:
				ans += d[j] - i
				d.remove(d[j])
				break
			if j == len(d) - 1:
				ans += arr[-1] + 1 - i
				arr += [arr[-1] + 1]
	elif d == []:
		ans += arr[-1] + 1 - i
		arr += [arr[-1] + 1]
print(ans)


n = int(input())
m = 0
l = 0
for i in sorted(map(int, input().split())):
	if l >= i:
		m += l - i + 1
		l += 1
	else:
		l = i
print(m)


n = int(input())
a = list(map(int, input().split()))
a.sort()
nxt = 0
ans = 0
for now in a:
	ans += max(0, nxt - now)
	nxt = max(nxt + 1, now + 1)
print(ans)


from collections import Counter
n = int(input())
aa = Counter([int(i) for i in input().split()])
coin = 0
keys = list(aa.keys())
for key in keys:
	key1 = key
	while aa[key] > 1:
		key1 += 1
		if aa[key1] == 0:
			aa[key1] = 1
			aa[key] -= 1
			coin += key1 - key
print(coin)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
pay = 0
for i in range(1, len(a)):
	if a[i] <= a[i - 1]:
		pay = pay + a[i - 1] + 1 - a[i]
		a[i] = a[i - 1] + 1
print(pay)


n = int(input())
a = [int(i) for i in input().split()]
vis = [False] * n
inc = 0
for i in range(n):
	if vis[a[i] - 1]:
		while a[i] in a[:i] or a[i] in a[i + 1:]:
			a[i] += 1
			inc += 1
	else:
		vis[a[i] - 1] = True
print(inc)


a = int(input())
x = [int(x) for x in input().split()]
x.sort()
c = 0
for i in range(1, a):
	if x[i] == x[i - 1]:
		x[i] = x[i] + 1
		c += 1
	elif x[i] < x[i - 1]:
		b = x[i - 1] - x[i]
		x[i] = x[i] + b + 1
		c = c + b + 1
print(c)


saisie = []
for i in range(1, 3):
	saisie.append([int(x) for x in input().split(' ')])
saisie[1].sort()
result = []
elt = saisie[1][0]
occ = 1
for i in saisie[1][1:]:
	if i == elt:
		occ = occ + 1
	else:
		result.append((elt, occ))
		occ = 1
		elt = i
result.append((elt, occ))
(prev_n, r) = (result[0][0], result[0][1] - 1)
cost = 0
for (n, occ) in result[1:]:
	ei = min(n - prev_n - 1, r)
	cost = cost + int(ei * (ei + 1) / 2)
	cost = cost + (r - ei) * (n - prev_n)
	r = r - ei + occ - 1
	prev_n = n
cost = cost + int(r * (r + 1) / 2)
print(cost)


n = int(input())
arr = [int(i) for i in input().split()]
s = set()
ans = 0
for i in arr:
	if i not in s:
		s.add(i)
	else:
		for j in range(i + 1, 2 * n + 1):
			if j not in s:
				ans += j - i
				s.add(j)
				break
print(ans)


n = int(input())
a = list(map(int, input().strip().split()))
a.sort()
b = a[0]
l = 0
for i in range(1, len(a)):
	if b >= a[i]:
		c = b - a[i] + 1
		l = l + c
		b = c + a[i]
	else:
		b = a[i]
print(l)


x = input()
numberBadges = int(x)
badgesList = [int(i) for i in input().split()]
coins = 0
badgesList.sort()
for i in range(0, numberBadges - 1):
	for j in range(i + 1, numberBadges):
		if badgesList[i] == badgesList[j]:
			badgesList[j] += 1
			coins += 1
print(coins)


n = int(input())
l = list(map(int, input().split()))
l.sort()
t = 0
t2 = 0
r = 0
for i in range(n):
	while l[i] + t2 <= t:
		t2 += 1
	r += t2
	l[i] = l[i] + t2
	t = l[i]
	t2 = 0
print(r)


n = int(input())
a = list(map(int, input().split()))
count = [0] * 10000
for i in range(len(a)):
	count[a[i]] += 1
c = 0
for i in range(len(count)):
	if count[i] > 1:
		while count[i] > 1:
			c += 1
			count[i] -= 1
			count[i + 1] += 1
print(c)


from collections import Counter, defaultdict
from sys import stdin, stdout
input = stdin.readline
I = lambda : int(input())
M = lambda : map(int, input().split())
LI = lambda : list(map(int, input().split()))
n = I()
a = LI()
a.sort()
b = []
d = defaultdict(int)
d = Counter(a)
for i in d.keys():
	b += [i] * (d[i] - 1)
c = []
i = a[0]
j = 0
while len(c) < len(b):
	if d[i] == 0 and b[j] < i:
		c += [i]
		j += 1
	i += 1
ans = 0
for i in range(len(b)):
	ans += abs(b[i] - c[i])
print(ans)


n = int(input())
l = list(map(int, input().split()))
l.sort()
ct = 0
for i in range(1, len(l)):
	if l[i] == l[i - 1]:
		l[i] += 1
		ct += 1
	elif l[i] < l[i - 1]:
		diff = abs(l[i - 1] - l[i])
		l[i] = l[i - 1] + 1
		ct += diff + 1
print(ct)


c = int(input())
numbers = list(map(int, input().split()))
numbers.sort()
count = 0
for i in range(c):
	for j in range(i + 1, c):
		if numbers[i] == numbers[j]:
			numbers[j] += 1
			count += 1
print(count)


n = int(input())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
sign = 1
for (i, num) in enumerate(nums):
	if num >= sign:
		sign = num
	else:
		ans += sign - num
	sign += 1
print(ans)


n = int(input())
bs = list(map(int, input().split()))
assert len(bs) == n
bs = sorted(bs)
last = -1
cost = 0
for b in bs:
	if b <= last:
		diff = last - b
		b += diff + 1
		cost += diff + 1
	last = b
print(cost)


n = int(input())
ans = 0
a = [int(_) for _ in input().split()]
a.sort()
for i in range(1, n):
	if a[i] == a[i - 1]:
		a[i] += 1
		ans += 1
	elif a[i] < a[i - 1]:
		temp = a[i - 1] - a[i] + 1
		a[i] += temp
		ans += temp
print(ans)


n = int(input())
sol = [int(x) for x in input().split()]
sol = sorted(sol)
count = 0
for i in range(n - 1):
	while sol[i] >= sol[i + 1]:
		sol[i + 1] += 1
		count += 1
print(count)


a = int(input()) - 1
b = sorted(map(int, input().split()))
p = 0
c = 0
while p < a:
	if b[p + 1] <= b[p]:
		c += b[p] - b[p + 1] + 1
		b[p + 1] = b[p] + 1
	p += 1
print(c)


n = int(input())
l = sorted(list(map(int, input().split())))
sum = 0
for it in l:
	sum += it
i = 1
prev = l[0]
ans = 0
while i < len(l):
	if l[i] <= l[i - 1]:
		l[i] = l[i - 1] + 1
	i += 1
sum2 = 0
for it in l:
	sum2 += it
print(sum2 - sum)


n = int(input())
a = sorted(map(int, input().split()))
cur = a[0] + 1
res = 0
for (idx, val) in enumerate(a[1:], start=1):
	if val <= cur:
		res += cur - val
		cur += 1
	else:
		cur = val + 1
print(res)


n = int(input())
a = list(map(int, input().split()))
l = [0] * 100000
for i in range(n):
	l[a[i]] += 1
col = 0
for i in range(len(l)):
	while l[i] > 1:
		l[i] -= 1
		l[i + 1] += 1
		col += 1
print(col)


n = int(input())
A = sorted(list(map(int, input().split())))
cant = 0
for k in range(1, n):
	if A[k] == A[k - 1]:
		A[k] += 1
		cant += 1
	elif A[k - 1] > A[k]:
		cant += A[k - 1] - A[k] + 1
		A[k] += A[k - 1] - A[k] + 1
print(cant)


n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
tmp = l[0]
for i in range(1, n):
	while tmp >= l[i]:
		l[i] += 1
		ans += 1
	tmp = l[i]
print(ans)


n = int(input())
lisa = list(map(int, input().split(' ')))
pan = [0] * n
for i in lisa:
	pan[i - 1] = pan[i - 1] + 1
buy = 0
for k in range(n - 1):
	if pan[k] > 1:
		buy += pan[k] - 1
		pan[k + 1] = pan[k + 1] + pan[k] - 1
buy += pan[n - 1] * (pan[n - 1] - 1) // 2
print(buy)


import os
import sys
from math import *
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def array():
	return [int(i) for i in input().split()]
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
n = int(input())
a = sorted(array())
b = a[:]
ans = 0
for i in range(1, n):
	if a[i] <= a[i - 1]:
		a[i] = a[i - 1] + 1
for i in range(n):
	ans += abs(a[i] - b[i])
print(ans)


n = int(input())
arr = list(map(int, input().split()))
dp = [0 for _ in range(n)]
add = 0
coins = 0
for i in range(n):
	dp[arr[i] - 1] += 1
for i in range(n):
	add += dp[i] - 1
	if add < 0:
		add = 0
	coins += add
while add > 0:
	add -= 1
	coins += add
print(coins)


n = int(input())
a = [int(x) for x in input().split()]
coin = 0
a.sort()
for i in range(1, n):
	while a[i] <= a[i - 1]:
		coin += 1
		a[i] += 1
print(coin)


n = int(input())
num = list(map(int, input().split()))
num.sort()
ans = ind = 0
for x in num:
	if x > ind:
		ind = x
	else:
		ind += 1
		ans += ind - x
print(ans)


n = int(input())
a = list(map(int, input().split()))
h = [0] * 30001
for i in a:
	h[i] += 1
count = 0
ans = 0
for i in range(1, 30001):
	if h[i] > 1:
		count += h[i] - 1
	if h[i] == 0 and count > 0:
		count -= 1
	if count > 0:
		ans += count
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
if len(set(a)) == 1:
	k = n - 1
	print(k * (k + 1) // 2)
else:
	co = 0
	for i in range(n - 1):
		if a[i] == a[i + 1]:
			a[i + 1] += 1
			co += 1
		elif a[i] > a[i + 1]:
			while True:
				if a[i + 1] > a[i]:
					break
				else:
					a[i + 1] += 1
					co += 1
	print(co)


n = int(input())
a = list(map(int, input().split()))
b = [0] * (n + 3001)
ans = 0
a.sort()
for i in range(0, len(a)):
	b[a[i]] += 1
for i in range(0, len(a)):
	if b[a[i]] >= 2:
		for l in range(1, n + 1):
			if b[a[i] + l] == 0:
				b[a[i] + l] = 1
				ans += l
				break
		b[a[i]] -= 1
print(ans)


n = int(input())
l = list(map(int, input().split()))
d = dict()
for i in l:
	if i not in d.keys():
		d[i] = 1
	else:
		d[i] += 1
x = 0
s = set()
y = list(d.keys())
y.sort()
for i in d.keys():
	while d[i] > 1:
		for j in range(i + 1, 100000):
			if j not in d.keys() and j not in s:
				x += j - i
				s.add(j)
				break
		d[i] -= 1
print(x)


input()
data = sorted(list(map(int, input().split(' '))))
temp = []
res = 0
front = '0'
flag = False
for i in data:
	if front == i:
		temp.append(front)
	else:
		j = 1
		if len(temp) != 0:
			flag = True
		while flag and j < i - front:
			temp_data = temp.pop()
			res += front + j - temp_data
			if len(temp) == 0:
				flag = False
			j += 1
		front = i
j = 1
for index in temp:
	res += data[-1] + j - index
	j += 1
print(res)


n = int(input())
a = [int(k) for k in input().split()]
a = sorted(a)
cost = sum(a)
for i in range(1, n):
	if a[i] <= a[i - 1]:
		a[i] = a[i - 1] + 1
print(sum(a) - cost)


n = int(input())
num = sorted(list(map(int, input().split())))
sum = 0
for i in range(1, n):
	if num[i] == num[i - 1]:
		sum += 1
		num[i] += 1
	elif num[i] < num[i - 1]:
		sum += num[i - 1] - num[i] + 1
		num[i] = num[i - 1] + 1
print(sum)


from sys import stdin

def r():
	return stdin.readline().strip()

def r_t(tp):
	return map(tp, r().strip().split())

def r_a(tp):
	return list(r_t(tp))

def solve(n, A):
	A.sort()
	(mod, ans) = (True, 0)
	while mod:
		mod = False
		for i in range(1, n):
			if A[i] <= A[i - 1]:
				copy = A[i]
				if A[i] == A[i - 1]:
					A[i] += 1
				else:
					A[i] = A[i - 1] + 1
				ans += A[i] - copy
	return ans

def main():
	n = int(r())
	A = list(r_t(int))
	print(solve(n, A))
main()


from sys import stdin, stdout
from collections import Counter

def ai():
	return list(map(int, stdin.readline().split()))

def ei():
	return map(int, stdin.readline().split())

def ip():
	return int(stdin.readline().strip())

def op(ans):
	return stdout.write(str(ans) + '\n')
n = ip()
li = ai()
li.sort()
c = 0
for i in range(1, n):
	if li[i] == li[i - 1]:
		li[i] += 1
		c += 1
	elif li[i] < li[i - 1]:
		c += li[i - 1] - li[i] + 1
		li[i] += li[i - 1] - li[i] + 1
op(c)


n = int(input())
cf = list(map(int, input().split()))
cf_list = [0 for i in range(6000 + 1)]
for c in cf:
	cf_list[c] += 1
ans = 0
for i in range(6000 + 1):
	if cf_list[i] > 1:
		ans += cf_list[i] - 1
		cf_list[i + 1] += cf_list[i] - 1
print(ans)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
for i in range(n - 1):
	if a[i] >= a[i + 1]:
		ans += a[i] - a[i + 1] + 1
		a[i + 1] = a[i] + 1
print(ans)


SIZE = 10
matrix = [[0] * SIZE for i in range(SIZE)]
array = [0] * SIZE
(n, ans) = (int(input()), 0)
arr = list(map(int, input().split()))
arr.sort()
for i in range(1, n):
	while arr[i] <= arr[i - 1]:
		arr[i] += 1
		ans += 1
print(ans)


from collections import Counter
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
k = sum(l)
s = l[0]
p = l[0]
for i in range(1, n):
	if l[i] <= p:
		p += 1
		s += p
	else:
		s = s + l[i]
		p = l[i]
print(abs(s - k))


n = int(input())
a = list(map(int, input().split()))
a.sort()
b = [0] * 6005
ans = 0
for i in a:
	if b[i] == 0:
		b[i] = 1
	else:
		while b[i] != 0:
			i += 1
			ans += 1
		b[i] = 1
print(ans)


n = int(input())
l = []
s = set()
for i in input().split():
	l.append(int(i))
l.sort()
counter = 0
for i in l:
	if i in s:
		j = i + 1
		while j in s:
			j += 1
		s.add(j)
		counter += j - i
	else:
		s.add(i)
print(counter)


from sys import stdin
num = int(stdin.readline().strip())
badges = sorted([int(i) for i in stdin.readline().strip().split()])
ans = 0
for i in range(num - 1):
	diff = 0 if badges[i] < badges[i + 1] else badges[i] - badges[i + 1] + 1
	ans += diff
	badges[i + 1] += diff
print(ans)


n = int(input())
a = list(map(int, input().split()))
a.sort()
ans = 0
for i in range(n - 1):
	if a[i] >= a[i + 1]:
		t = a[i + 1]
		a[i + 1] += a[i] - a[i + 1] + 1
		ans += a[i] - t + 1
print(ans)


def lmap():
	return list(map(int, input().split()))
n = int(input())
w = lmap()
w.sort()
cnt = 0
for i in range(1, n):
	if w[i] <= w[i - 1]:
		cnt += abs(w[i - 1] + 1 - w[i])
		w[i] = w[i - 1] + 1
print(cnt)


def main():
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	ans = 0
	for i in range(1, len(a)):
		if a[i] == a[i - 1]:
			for j in range(i + 1, len(a)):
				if a[i] != a[j]:
					break
				a[j] += 1
				ans += 1
			a[i] += 1
			ans += 1
	print(ans)
main()


n = int(input())
list1 = list(map(int, input().split()))
a = [0] * (n + 1)
result = 0
list2 = []
for i in list1:
	if a[i] == 0:
		a[i] = i
	else:
		list2.append(i)
if len(list2) == 0:
	print(0)
else:
	list2.sort()
	mins = list2[0]
	for i in range(mins, n + 1):
		if a[i] == 0:
			if list2[0] <= i:
				result += i - list2[0]
				list2.pop(0)
	for i in range(len(list2)):
		result += n + i + 1 - list2[i]
	print(result)


(n, v, res) = (int(input()), [int(i) for i in input().split()], 0)
v.sort()
for i in range(n):
	if i > 0 and v[i] <= v[i - 1]:
		res += v[i - 1] + 1 - v[i]
		v[i] = v[i - 1] + 1
print(res)


n = int(input())
cl = [int(v) for v in input().split()]
cl = sorted(cl)
cost = 0
has = set()
minv = 0
for v in cl:
	if v not in has:
		has.add(v)
	else:
		while v in has:
			v += 1
			cost += 1
		has.add(v)
print(cost)


n = int(input())
b = set()
a = [int(s) for s in input().split()]
res = 0
for i in a:
	if not i in b:
		b.add(i)
	else:
		while True:
			res += 1
			i += 1
			if not i in b:
				b.add(i)
				break
print(res)


import sys
input = lambda : sys.stdin.readline().strip()
li = lambda : list(map(int, input().split()))
I = lambda : int(input())
n = I()
l = li()
l.sort()
badge = set()
ans = 0
for i in l:
	while i in badge:
		i += 1
		ans += 1
	else:
		badge.add(i)
print(ans)


n = int(input())
A = list(map(int, input().split()))
A.sort()
con = 0
for i in range(n - 1):
	if A[i] == A[i + 1]:
		A[i + 1] += 1
		con += 1
	elif A[i] > A[i + 1]:
		k = A[i] - A[i + 1]
		A[i + 1] += k + 1
		con += k + 1
print(con)


n = int(input())
i = list(map(int, input().split()))
r = [0] * (n + 1)
for x in i:
	r[x] += 1
t = []
s = 0
for (j, x) in enumerate(r):
	if j == 0:
		continue
	if x > 1:
		t += [j] * (x - 1)
	elif x == 0 and t:
		el = t.pop()
		s += j - el
for (j, x) in enumerate(t):
	s += n + j + 1 - x
print(s)


n = int(input())
a = sorted(map(int, input().split()))
pre = -1
ans = 0
for x in a:
	if x <= pre:
		ans += pre - x + 1
		x = pre + 1
	pre = x
print(ans)


import sys
import math
a = []
N = int(input())
a = [int(x) for x in input().split()]
a.sort()
ans = 0
for i in reversed(range(N)):
	temp = 0
	for j in range(i):
		if -a[i] + a[j] + i - j > temp:
			temp = -a[i] + a[j] + i - j
	ans += temp
print(ans)


read = lambda : list(map(int, input().split()))
n = read()
A = read()
used = [0] * 6001
u = [0] * 6001
cnt = 0
A = sorted(A)
used[0] = 1
for i in A:
	used[i] = 1
for i in A:
	if u[i] == 0:
		u[i] = 1
	else:
		for j in range(6001):
			if used[j] == 0 and j > i:
				cnt += abs(j - i)
				used[j] = 1
				break
print(cnt)


n = int(input())
arr = list(map(int, input().split()))
ans = 0
arr.sort()
for i in range(1, n):
	if arr[i] == arr[i - 1]:
		arr[i] += 1
		ans += 1
	elif arr[i] < arr[i - 1]:
		temp = arr[i]
		arr[i] = arr[i - 1] + 1
		ans += arr[i] - temp
print(ans)


import math
n = int(input())
a = [int(i) for i in input().split()]
a = sorted(a)
sum = 0
for i in range(0, len(a)):
	if i == 0:
		pass
	elif a[i] <= a[i - 1]:
		sum = sum + (abs(a[i - 1] + 1) - a[i])
		a[i] = a[i] + (abs(a[i - 1] + 1) - a[i])
	else:
		pass
print(sum)


n = int(input())
a = [int(s) for s in input().split()]
a.sort()
c = 0
j = 0
for i in range(1, n):
	if a[i - 1] >= a[i]:
		c += a[i - 1] - a[i] + 1
		a[i] += a[i - 1] - a[i] + 1
print(c)


class CodeforcesTask546BSolution:

	def __init__(self):
		self.result = ''
		self.badges = []

	def read_input(self):
		input()
		self.badges = [int(x) for x in input().split(' ')]

	def process_task(self):
		self.badges.sort()
		cost = 0
		for x in range(1, len(self.badges)):
			if self.badges[x] <= self.badges[x - 1]:
				cost += self.badges[x - 1] - self.badges[x] + 1
				self.badges[x] = self.badges[x - 1] + 1
		self.result = str(cost)

	def get_result(self):
		return self.result
Solution = CodeforcesTask546BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


t = int(input())
l = list(map(int, input().rstrip().split(' ')))
l.sort()
total = 0
for i in range(1, t):
	if l[i] <= l[i - 1]:
		total += l[i - 1] - l[i] + 1
		l[i] = l[i] + l[i - 1] - l[i] + 1
print(total)


n = int(input())
arr = [int(x) for x in input().split()]
total = 0
arr1 = [0] * (2 * n + 1)
for i in arr:
	arr1[i] += 1
	if arr1[i] > 1:
		j = i + 1
		while True:
			if arr1[j] == 0:
				arr1[j] = 1
				total += j - i
				break
			j += 1
print(total)


n = int(input())
a = list(map(int, input().split()))
(v, p) = (0, 0)
for i in sorted(a):
	v += max(0, p - i + 1)
	p = max(p + 1, i)
print(v)


n = int(input())
l1 = list(map(int, input().split()))
l1.sort()
sum1 = 0
for i in range(len(l1) - 1):
	for j in range(i + 1, len(l1)):
		if l1[i] == l1[j]:
			sum1 += 1
			l1[j] += 1
print(sum1)


from collections import Counter
(n, c) = (int(input()), Counter(map(int, input().split())))
cost = 0
for i in range(1, n):
	extra = max(0, c[i] - 1)
	(cost, c[i + 1]) = (cost + extra, c[i + 1] + extra)
print(cost + c[n] * (c[n] - 1) // 2)


n = int(input())
A = list(map(int, input().split()))
A.sort()
prev = -1
res = 0
for x in A:
	if x > prev:
		prev = x
	else:
		prev = prev + 1
		res += prev - x
print(res)


input()
listNum = list(map(int, input().split()))
setNum = set()
totalMoney = 0
for i in listNum:
	if i not in setNum:
		setNum.add(i)
	else:
		while i in setNum:
			i += 1
			totalMoney += 1
		setNum.add(i)
print(totalMoney)


N = int(input())
badges = [int(badge) for badge in input().split()]
badges.sort()
next_free = badges[-1] + 1
frees = []
occurences = [0] * (N + 1)
for badge in badges:
	occurences[badge] += 1
for i in range(badges[0] + 1, badges[-1]):
	if i not in badges:
		frees.append(i)
if frees == []:
	flag = True
else:
	flag = False
coin = 0
for badge in range(badges[0], badges[-1] + 1):
	if occurences[badge] == 1:
		continue
	for i in range(0, occurences[badge] - 1):
		if flag:
			coin += next_free - badge
			next_free += 1
		else:
			free = -1
			while free < badge:
				free = frees.pop(0)
				if frees == []:
					flag = True
					break
			if free > badge:
				coin += free - badge
			else:
				coin += next_free - badge
				next_free += 1
print(coin)


n = int(input())
a = [*map(int, input().split())]
a.sort()
d = {}
count = 0
for i in a:
	if d.get(i) == None:
		d[i] = 1
	else:
		while True:
			i += 1
			count += 1
			if d.get(i) == None:
				d[i] = 1
				break
print(count)


import math
import bisect
import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
n = inp()
A = inlt()
out = 0
hashh = {}
for i in range(n):
	for j in range(A[i], 2 * n):
		if j not in hashh:
			hashh[j] = True
			out += j - A[i]
			break
print(out)


n = int(input())
As = list(map(int, input().split()))
freq = [0] * (2 * n + 1)
for a in As:
	freq[a - 1] += 1
count = 0
for i in range(2 * n + 1):
	if freq[i] < 2:
		continue
	delta = freq[i] - 1
	count += delta
	freq[i + 1] += delta
print(count)


n = int(input())
a = [int(x) for x in input().split()]
a.sort()
mini = a[0]
coins = 0
for i in range(1, n):
	if a[i] <= mini:
		coins += mini + 1 - a[i]
		mini = mini + 1
	else:
		mini = a[i]
print(coins)


from sys import stdin, stdout, setrecursionlimit
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return input()

def num():
	return int(input())

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]

def pmat(A):
	for ele in A:
		print(*ele, end='\n')

def seive():
	prime = [1 for i in range(10 ** 6 + 1)]
	prime[0] = 0
	prime[1] = 0
	for i in range(10 ** 6 + 1):
		if prime[i]:
			for j in range(2 * i, 10 ** 6 + 1, i):
				prime[j] = 0
	return prime
n = int(data())
arr = L()
hashtable = {i: 0 for i in arr}
ans = 0
i = 0
for i in range(n):
	if not hashtable[arr[i]]:
		hashtable[arr[i]] = 1
	else:
		while arr[i] in hashtable:
			arr[i] += 1
			ans += 1
		hashtable[arr[i]] = 0
print(ans)
endtime = time.time()


n = int(input())
arr = sorted(list(map(int, input().split())))
count = 0
counter = 0
for i in range(1, n):
	if arr[i] <= arr[i - 1]:
		count = arr[i - 1] - arr[i] + 1
		arr[i] += count
		counter += count
print(counter)


def main():
	n = int(input())
	ip = [int(item) for item in input().split(' ')]
	ip.sort()
	prev = ip[0]
	coins = 0
	n_coins = 0
	for i in range(1, len(ip)):
		if ip[i] == prev:
			coins += 1
			ip[i] += 1
		elif ip[i] < prev:
			n_coins = prev - ip[i] + 1
			coins += n_coins
			ip[i] += n_coins
		prev = ip[i]
	print(coins)
main()


__author__ = 'trunghieu11'
n = int(input())
A = list(map(int, input().split()))
A.sort()
answer = 0
for i in range(1, n):
	increase = max(0, A[i - 1] - A[i] + 1)
	A[i] += increase
	answer += increase
print(answer)


n = int(input())
s = input().split()
a = [0] * 3005
for i in range(0, n):
	j = int(s[i])
	a[j] = a[j] + 1
count = 0
ret = 0
for i in range(1, n + 1):
	count += a[i]
	if count == 0:
		continue
	count = count - 1
	ret = ret + count
ret += int(count * (count - 1) / 2)
print(ret)


n = int(input())
a = list(map(int, input().split()))
d = [0] * (n + 2)
f = 0
for i in range(n):
	d[a[i]] += 1
for i in range(1, n + 1):
	if d[i] > 1:
		f += d[i] - 1
		d[i + 1] += d[i] - 1
f += (d[n + 1] - 1) * d[n + 1] // 2
print(f)


line = input()
a = [int(i) for i in input().split(' ')]
a = sorted(a)

def solve(a):
	sum = 0
	sum1 = 0
	current_num = 0
	for num in a:
		if current_num < num:
			current_num = num
		else:
			current_num += 1
		sum += num
		sum1 += current_num
	print(sum1 - sum)
solve(a)


n = int(input())
num = []
for i in range(30000):
	num.append(0)
mass = []
mass = input().split(' ')
for i in range(n):
	num[int(mass[i]) - 1] += 1
score = 0
for i in range(n):
	while num[i] > 1:
		j = i + 1
		while num[j] != 0:
			j += 1
		score += j - i
		num[i] -= 1
		num[j] += 1
print(score)


n = int(input())
a = list(map(int, input().split()))
s = sum(a)
a.sort()
for i in range(1, len(a)):
	if a[i - 1] >= a[i]:
		a[i] = a[i - 1] + 1
print(sum(a) - s)


from sys import stdin, stdout
from collections import Counter
nmbr = lambda : int(stdin.readline())
lst = lambda : list(map(int, stdin.readline().split()))
for _ in range(1):
	n = nmbr()
	ans = 0
	a = lst()
	d = Counter(a)
	for i in range(n):
		if d[a[i]] == 1:
			continue
		mx = a[i] + 1
		while mx in d:
			mx += 1
		ans += mx - a[i]
		d[mx] = d.get(mx, 0) + 1
		d[a[i]] -= 1
	print(ans)