В стратегической компьютерной игре «Settlers II» для расширения и охраны своей территории необходимо строить защитные сооружения. Рассмотрим одно из таких сооружений. В текущий момент данное защитное сооружение вмещает в себя ровно n солдат. В рамках данной задачи можно считать, что количество солдат в этом защитном сооружении не будет ни увеличиваться, ни уменьшаться.

Каждый солдат имеет звание — некоторое натуральное число от 1 до k. 1 — рядовой, k — генерал. Чем выше звание у солдата, тем лучше он сражается. Поэтому для игрока выгодно иметь солдат как можно более высокого звания.

Для повышения званий солдат нужно тренировать. Просто так солдаты тренироваться не будут, и для каждой тренировки нужна одна золотая монета. На каждой тренировке присутствуют все n солдат.

В конце каждой из тренировок звания солдат повышаются следующим образом. Сначала все солдаты разбиваются на группы с одинаковым званием так, чтобы получилось наименьшее возможное количество групп. Затем в каждой из таких групп, где находятся солдаты звания ниже k, ровно один из солдат повышает свое звание на единицу.

Вам известны звания всех n солдат на текущий момент. Определите количество золотых монет, нужных для повышения званий всех солдат до звания k.