У полковника есть n значков. Он хочет дать по значку каждому из n его солдатов. У каждого значка есть коэффициент крутизны, который показывает уровень, достигнутый владельцем значка. Коэффициент крутизны можно увеличить на 1 за одну монету.

Для каждой пары солдат один из них должен получить значок, коэффициент которого строго выше второго. Для солдат не важно, какие у них значения коэффициента, требуется лишь, чтобы их коэффициенты отличались друг от друга.

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