E. Тамада Соня
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сова Соня решила стать тамадой. Для этого она собрала своих друзей сов на даче. Соня поставила в круг m стульев и последовательно пронумеровала их от 1 до m. Таким образом, стулья i и i + 1 являются соседними для всех i от 1 до m - 1. Также соседними являются стулья 1 и m. На некоторых стульях сидят её друзья, их всего n. Никакие два друга не сидят на одном стуле. Соня придумала следующие правила:

  1. Каждый из участников убирает из игры стул, на котором он сейчас сидит.
  2. Каждый из участников выбирает направление, в котором он будет двигаться, — по часовой стрелке (возрастание номеров, из m переход в 1) или против часовой (убывание номеров, из 1 переход в m). Эти направления могут совпадать или различаться для двух произвольных сов.
  3. Каждый ход гости двигаются на одну позицию в выбранном направлении. Если там находится стул, то он убирается из игры.
  4. Игра заканчивается, когда в кругу не остаётся ни одного стула.

У всех сов есть свои дела, поэтому они хотят закончить игру как можно быстрее. Гости договариваются, кто в каком направлении идет. Их задача — за минимально возможное количество ходов завершить игру. Помогите им в этом.

Входные данные

Первая строка входных данных содержит единственное число m (1 ≤ m ≤ 109) — длину круга.

Вторая строка содержит единственное число n (1 ≤ n ≤ 100 000) — количество друзей.

Следующая строка содержит возрастающую последовательность из n чисел ai (1 ≤ ai ≤ m) — начальные позиции друзей сов.

Выходные данные

Выведите минимальное количество ходов, за которое совы могут завершить игру. В том числе ответом может быть число 0.

Примеры
Входные данные
6
3
1 3 5
Выходные данные
1
Входные данные
6
2
1 6
Выходные данные
2
Входные данные
406
6
1 2 3 204 205 206
Выходные данные
100
Примечание

В первом примере это возможно, если все совы будут двигаться по часовой стрелке, то есть в направлении возрастания номеров позиций.

Во втором примере первой сове требуется двигаться по часовой стрелке, а второй — против.

В третьем примере первая и четвертая сова должны двигаться против часовой стрелки, третья и шестая — по часовой, а вторая и пятая могут двигаться как угодно.