Некоторые люди обожают решать контесты по спортивному программированию, Дина же увлекается фотографией. Как только Байтландский ботанический сад объявил о старте Летней выставки энотер, она решила попробовать свою новую камеру в действии.

На выставке представлены $$$l = 10^{100}$$$ энотер, выставленных в ряд, и пронумерованных от $$$0$$$ до $$$l - 1$$$. Объектив камеры позволяет сделать снимок с ровно $$$w$$$ цветами, то есть Дина может снять любую фотографию, содержащую цветы с номерами с $$$x$$$ по $$$x + w - 1$$$ для некоторого целого $$$x$$$ от $$$0$$$ до $$$l - w$$$. Такую фотографию мы будем обозначать как $$$[x, x + w - 1]$$$.

Во время выставки она сделала $$$n$$$ фотографий, $$$i$$$-я по порядку фотография в наших обозначениях выглядит как $$$[x_i, x_i + w - 1]$$$. Увидев, что вечером энотеры раскрываются, она решила сделать видео с замедленной съемкой (time-lapse) из этих фотографий.

Процесс заключается в следующем: Дина обрезает фотографии, оставляя от каждой из них подотрезок, состоящий ровно из $$$k$$$ цветов, составляет из них видео, сохраняя порядок их следования, и вуаля — произведение искусства готово!

Назовем сценой непрерывную последовательность фотографий такую, что множество цветов на них совпадает. Изменение множества цветов между двумя сценами мы назовем склейкой. Например, пусть на первой фотографии запечатлены цветы $$$[1, 5]$$$, на второй — $$$[3, 7]$$$, а на третьей — $$$[8, 12]$$$. Если $$$k = 3$$$, то можно вырезать на первой и второй фотографии отрезок цветов $$$[3, 5]$$$, а на третьей фотографии — отрезок цветов $$$[9, 11]$$$. Тогда первые две фотографии образуют одну сцену, третья фотография образует вторую сцену, а изменение между этими сценами, которое происходит между второй и третьей фотографией — склейка. Если же $$$k = 4$$$, то каждый из двух переходов между фотографиями вынужден быть склейкой.

Дина хочет, чтобы количество склеек на итоговом видео было минимально. Помогите ей! Посчитайте минимальное количество склеек для разных значений $$$k$$$.