Сова Соня решила стать тамадой. Для этого она собрала своих друзей сов на даче. Соня поставила в круг m стульев и последовательно пронумеровала их от 1 до m. Таким образом, стулья i и i + 1 являются соседними для всех i от 1 до m - 1. Также соседними являются стулья 1 и m. На некоторых стульях сидят её друзья, их всего n. Никакие два друга не сидят на одном стуле. Соня придумала следующие правила:
- Каждый из участников убирает из игры стул, на котором он сейчас сидит.
- Каждый из участников выбирает направление, в котором он будет двигаться, — по часовой стрелке (возрастание номеров, из m переход в 1) или против часовой (убывание номеров, из 1 переход в m). Эти направления могут совпадать или различаться для двух произвольных сов.
- Каждый ход гости двигаются на одну позицию в выбранном направлении. Если там находится стул, то он убирается из игры.
- Игра заканчивается, когда в кругу не остаётся ни одного стула.
У всех сов есть свои дела, поэтому они хотят закончить игру как можно быстрее. Гости договариваются, кто в каком направлении идет. Их задача — за минимально возможное количество ходов завершить игру. Помогите им в этом.
Выходные данные
Выведите минимальное количество ходов, за которое совы могут завершить игру. В том числе ответом может быть число 0.
Примечание
В первом примере это возможно, если все совы будут двигаться по часовой стрелке, то есть в направлении возрастания номеров позиций.
Во втором примере первой сове требуется двигаться по часовой стрелке, а второй — против.
В третьем примере первая и четвертая сова должны двигаться против часовой стрелки, третья и шестая — по часовой, а вторая и пятая могут двигаться как угодно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
3
1 3 5
|
1
|
|
2
|
6
2
1 6
|
2
|
|
3
|
406
6
1 2 3 204 205 206
|
100
|