На круге находятся \(n\) домов с номерами от \(1\) до \(n\). Для каждого \(1 \leq i \leq n - 1\) дом \(i\) и дом \(i + 1\) являются соседями; кроме того, дом \(n\) и дом \(1\) также являются соседями.
Изначально \(m\) из этих \(n\) домов заражены смертельным вирусом. Каждое утро Cirno может выбрать незараженный дом и навсегда защитить его от заражения.
Каждый день по порядку происходят следующие вещи:
- Cirno выбирает незараженный дом и защищает его навсегда.
- Заражаются все незараженные и незащищенные дома, у которых есть хотя бы один зараженный сосед.
Cirno хочет остановить распространение вируса. Найдите минимальное количество домов, которые в итоге будут заражены, если вы оптимально выберете дома для защиты.
Обратите внимание, что каждый день Cirno всегда выбирает дом для защиты до распространения вируса. Также защищенный дом не будет никогда заражен.
Выходные данные
Для каждого набора входных данных в отдельной строке выведите целое число — минимальное количество зараженных домов в итоге.
Примечание
В первом наборе входных данных получить ответ можно следующим образом:
В начале первого дня заражены дома \(3\), \(6\), \(8\). Выберите дом \(2\) для защиты.
В начале второго дня заражены дома \(3\), \(4\), \(5\), \(6\), \(7\), \(8\), \(9\). Выберите дом \(10\) для защиты.
В начале третьего дня зараженных домов больше нет.
Во втором наборе входных данных получить ответ можно следующим образом:
В начале первого дня заражены дома \(2\), \(5\). Выберите дом \(1\) для защиты.
В начале второго дня заражены дома \(2\), \(3\), \(4\), \(5\), \(6\). Не осталось незащищенных и незараженных домов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
10 3
3 6 8
6 2
2 5
20 3
3 7 12
41 5
1 11 21 31 41
10 5
2 4 6 8 10
5 5
3 2 5 4 1
1000000000 1
1
1000000000 4
1 1000000000 10 16
|
7
5
11
28
9
5
2
15
|