В стратегической компьютерной игре «Settlers II» для расширения и охраны своей территории необходимо строить защитные сооружения. Рассмотрим одно из таких сооружений. В текущий момент данное защитное сооружение вмещает в себя ровно n солдат. В рамках данной задачи можно считать, что количество солдат в этом защитном сооружении не будет ни увеличиваться, ни уменьшаться.
Каждый солдат имеет звание — некоторое натуральное число от 1 до k. 1 — рядовой, k — генерал. Чем выше звание у солдата, тем лучше он сражается. Поэтому для игрока выгодно иметь солдат как можно более высокого звания.
Для повышения званий солдат нужно тренировать. Просто так солдаты тренироваться не будут, и для каждой тренировки нужна одна золотая монета. На каждой тренировке присутствуют все n солдат.
В конце каждой из тренировок звания солдат повышаются следующим образом. Сначала все солдаты разбиваются на группы с одинаковым званием так, чтобы получилось наименьшее возможное количество групп. Затем в каждой из таких групп, где находятся солдаты звания ниже k, ровно один из солдат повышает свое звание на единицу.
Вам известны звания всех n солдат на текущий момент. Определите количество золотых монет, нужных для повышения званий всех солдат до звания k.
Примечание
В первом примере повышение званий солдат будет происходить следующим образом:
1 2 2 3 → 2 2 3 4 → 2 3 4 4 → 3 4 4 4 → 4 4 4 4
Итого 4 тренировки, на которые требуется 4 золотые монеты.