Задача №113619. Нужно больше конфет! (Э)
У Карлсона дома есть набор из n банок с конфетами. Банки пронумерованы от 1 до n , в i -й из них лежит a i конфет. Карлсон считает набор банок симпатичным , если в этом наборе нет трех банок с разным числом конфет.
У Карлсона есть неограниченный запас конфет в карманах, поэтому он может добавить в любую банку произвольное число конфет. Помогите ему определить, какое минимальное общее число конфет ему придется добавить, чтобы набор банок с конфетами стал симпатичным.
Первая строка входных данных содержит натуральное число n ( 1 ≤ n ≤ 10 5 ) — количество банок в наборе Карлсона.
Вторая строка входных данных содержит n целых чисел a i ( 0 ≤ a i ≤ 10 9 ) — число конфет в банках. Соседние числа отделены друг от друга одним пробелом.
Выведите одно число — минимальное общее количество конфет, которое придется добавить, чтобы Карлсон считал набор банок симпатичным.
В первом тесте из примера Карлсон может добавить в первую банку две конфеты, а во вторую банку — одну конфету. Тогда в первой и четвертой банках будет лежать по 7 конфет, а во второй и третьей — по 2 конфеты.
Во втором тесте из примера набор банок исходно является симпатичным, добавлять конфеты не требуется.
4 5 1 2 7
3
3 1 1 1
0