У Тёти Люсине, как и у всех гениальных людей, имеются свои странности. Сегодня в качестве развлечения она решила посмотреть на противостояние двух могущественных функций. В зависимости от результата она решит, добавлять ли эти функции в CrowdScript.
Дан массив \(a\) из \(n\) неотрицательных целых чисел. За одну операцию вы можете заменить любое число в массиве на любое неотрицательное целое число.
Назовём стоимостью массива \(\operatorname{DIFF}(a) - \operatorname{MEX}(a)\), где \(\operatorname{MEX}\) множества чисел — это минимальное целое неотрицательное число, которого нет в множестве, а \(\operatorname{DIFF}\) — количество различных чисел в массиве.
Например, \(\operatorname{MEX}(\{1, 2, 3\}) = 0\), \(\operatorname{MEX}(\{0, 1, 2, 4, 5\}) = 3\).
Вам необходимо определить, какую минимальную стоимость массива \(a\) можно получить, если разрешено сделать не больше \(k\) операций.
Выходные данные
Для каждого набора входных данных выведите единственное число — минимальная стоимость, которую можно получить, сделав не больше \(k\) операций.
Примечание
В первом наборе входных данных не требуется делать какие-либо операции, чтобы минимизировать \(\operatorname{DIFF} - \operatorname{MEX}\).
Во втором наборе входных данных можно заменить \(5\) на \(1\). После этого массив \(a\) будет \([0,\, 2,\, 4,\, 1]\), \(\operatorname{DIFF} = 4\), \(\operatorname{MEX} = \operatorname{MEX}(\{0, 1, 2, 4\}) = 3\), поэтому ответ равен \(1\).
В третьем наборе входных данных один из возможных массивов \(a\) будет \([4,\, 13,\, 0,\, 0,\, 13,\, 1,\, 2]\), \(\operatorname{DIFF} = 5\), \(\operatorname{MEX} = 3\).
В четвертом наборе входных данных один из возможных массивов \(a\) будет \([1,\, 2,\, 3,\, 0,\, 0,\, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
4 1
3 0 1 2
4 1
0 2 4 5
7 2
4 13 0 0 13 1337 1000000000
6 2
1 2 8 0 0 0
|
0
1
2
0
|