На координатной прямой находятся одна кошка, \(k\) мышек и одна норка. Кошка находится в точке \(0\), а норка в точке \(n\). Все мышки находятся между кошкой и норкой: \(i\)-я мышка расположена в точке \(x_i\) (\(0 < x_i < n\)), в одной точке может находиться много мышек.
За одну единицу времени происходит следующее. Сначала ровно одна любая мышка передвигается вправо на \(1\). Если эта мышка оказалась в норке, то она в ней прячется (т. е. больше никуда данная мышка передвигаться не будет и кошка не сможет её съесть). Затем (после того, как мышка завершила своё передвижение) кошка передвигается вправо на \(1\). Если в точке назначения кошки есть мышки, то кошка их съедает (они затем передвигаться не смогут). Процесс продолжается до тех пор, пока каждая мышка не будет спрятана или съедена.
Иными словами, сначала ход делает одна из мышек. Если мышка спряталась в норке, то она спаслась. Затем кошка делает ход. Кошка съедает тех мышек, которые находятся в точке, куда она сделала ход (если кошка «приземлилась» в норке, то она никого не съедает).
Каждую единицу времени вы можете выбрать мышку, которая в этот момент времени будет передвигаться. Какое максимальное количество мышек может добраться до норки, не будучи съеденными?
Выходные данные
Для каждого набора входных данных в отдельной строке выведите одно число \(m\) (\(m \ge 0\)) — максимальное количество мышек, которые могут добраться до норки, не будучи съеденными.