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