Рабочий день Поликарпа длится ровно \(n\) минут. Поликарп очень любит шоколадные батончики Барс. Он может съесть один батончик ровно за минуту. Всего у Поликарпа есть \(k\) батончиков в начале рабочего дня.
В некоторые минуты рабочего дня у него важные дела и есть батончик в такие минуты он не может, в остальные же минуты он может есть батончик, а может и не есть. Известно, что в первую и последнюю минуты рабочего дня важных дел у него точно нет, и он обязательно съест батончики в них, чтобы порадовать себя в начале и в конце рабочего дня. Гарантируется, что \(k\) строго больше \(1\).
Перед вами стоит задача определить такой порядок поедания батончиков, чтобы время максимального перерыва между съеденными батончиками было как можно меньше.
Считайте, что если Поликарп съел батончик в минуту \(x\), а следующий батончик он съел в минуту \(y\) (\(x < y\)), то перерыв равен \(y - x - 1\) минутам. Поликарп не обязательно должен съедать все батончики.
Выходные данные
Выведите минимально возможное количество минут перерыва между поеданием батончиков Поликарпом.
Примечание
В первом примере Поликарп не может есть батончик во вторую минуту, поэтому перерыв будет равен одной минуте.
Во втором примере Поликарп обязательно съесть батончики в минуту \(1\) и в минуту \(8\), также ему нужно съесть батончик в минуту \(5\), тогда максимальный перерыв будет равен \(3\) минутам.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
010
|
1
|
|
2
|
8 3
01010110
|
3
|