ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

Чемпионат Урала 2011

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

I. Удар самурая

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Коган-сэнсэй продолжает обучать молодого Генноске Фуджики искусству владения мечом. Коган закрепил тонкий стебель бамбука длины l в горизонтальном положении на n опорах и приказал Генноске разрубить его на две части. По словам Когана, меч самурая должен быть настолько острым, а удар должен наноситься так быстро, что после удара обе части стебля должны остаться неподвижными.
Фуджики заметил, что, помимо мастерства самурая, имеет значение и место нанесения удара. Если центр масс одной из частей стебля не будет расположен между двумя опорами, то эта часть упадёт. Генноске предложил покрасить в белый цвет те участки стебля бамбука, после удара мечом по которым хотя бы одна из получившихся частей заведомо упадёт. Помогите ему вычислить суммарную длину участков стебля, которые нужно будет покрасить.

Исходные данные

В первой строке записаны целые числа l и n (3 ≤ l ≤ 109; 2 ≤ n ≤ 105). Во второй строке записаны n различных целых положительных чисел, меньших l — расстояния от левого конца стебля бамбука до опор, его поддерживающих. Опоры перечислены по порядку, от левого конца стебля к правому. Гарантируется, что изначально стебель расположен устойчиво.

Результат

Выведите суммарную длину участков стебля, которые Генноске должен покрасить в белый цвет, округлённую вверх до ближайшего целого числа.

Пример

исходные данныерезультат
5 4
1 2 3 4
4
Автор задачи: Денис Дублённых
Источник задачи: XV Открытый чемпионат Урала по спортивному программированию (апрель, 2011)
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 1838. Удар самурая