E. Настройка дронов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
PIXL - This Time
⠀

Вы управляете флотом из $$$n$$$ дронов, каждый из которых имеет уровень энергии $$$a_1, \ldots, a_n$$$. Вам также дано целое положительное число $$$k$$$, которое представляет собой максимальное количество дронов, которые могут иметь один и тот же уровень энергии.

Чтобы предотвратить перегрузки, дроны автоматически выполняют операции балансировки энергии следующим образом. Пока существует уровень энергии, который появляется строго более чем $$$k$$$ раз, они выполняют следующие шаги:

  • сначала каждый дрон $$$i$$$, уровень энергии которого $$$a_i$$$ появлялся ранее (то есть существует $$$j \lt i$$$, для которого $$$a_j = a_i$$$), помечается;
  • затем для каждого помеченного дрона его энергия увеличивается на $$$1$$$ единицу;
  • затем метки удаляются.

Процесс останавливается, как только ни один уровень энергии не появляется более чем $$$k$$$ раз. Определите, сколько операций балансировки энергии будет выполнено.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$, $$$k$$$ ($$$1 \leq k \leq n \leq 2 \cdot 10^5$$$) — количество дронов и максимальное допустимое количество дронов с одинаковым уровнем энергии.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2n$$$) — начальные уровни энергии дронов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одну строку, содержащую целое число: количество выполненных операций балансировки энергии.

Пример
Входные данные
5
6 3
1 1 1 1 1 1
5 1
1 3 2 1 4
6 2
1 1 1 2 3 3
4 1
8 8 8 8
2 2
1 2
Выходные данные
3
4
4
3
0
Примечание

В первом наборе входных данных уровни энергии дронов развиваются следующим образом:

  • в начале, $$$[1, 1, 1, 1, 1, 1]$$$;
  • после $$$1$$$ операции, $$$[1, 2, 2, 2, 2, 2]$$$;
  • после $$$2$$$ операций, $$$[1, 2, 3, 3, 3, 3]$$$;
  • после $$$3$$$ операций, $$$[1, 2, 3, 4, 4, 4]$$$.

После $$$3$$$ операций каждый уровень энергии появляется не более чем $$$3$$$ раза, поэтому процесс останавливается.

Во втором наборе входных данных уровни энергии изменяются следующим образом: $$$[1, 3, 2, 1, 4] \rightarrow [1, 3, 2, 2, 4] \rightarrow [1, 3, 2, 3, 4] \rightarrow [1, 3, 2, 4, 4] \rightarrow [1, 3, 2, 4, 5]$$$. Процесс останавливается после $$$4$$$ операций.