Емблема центру  www.olymp.vinnica.ua     netoi.org.ua
Центр олімпіад школярів в Iнтернеті
Likt-PMG17
м.Вiнниця


Годинник
 
Stairs

Лестница (stairs)

Как известно, Школа чародейства и волшебства в Хогвардсе имеет 142 лестницы, одна из которых имеет ровноN ступенек. Именно по этой лестнице можно передвигаться, переходя с одной ступеньки на следующую, перепрыгивая через ступеньку или перепрыгивая через две ступеньки, однако перепрыгивать через ступеньки два раза подряд нельзя. Часть ступенек была разрушена в одной из схваток с Волан де Мортом, однако лестницей все еще можно пользоваться, обязательно начиная движение с первой ступеньки и заканчивая на последней.

Альбус Дамблдор не на шутку обеспокоен состоянием этой лестницы и его интересует ответ на такой вопрос: при разрушении какого максимального количества ступенек по лестнице все еще можно будет подняться спервой ступеньки на последнюю.

Формат ввода-вывода:

Программа stairs читает с клавиатуры (стандартного устройства ввода) два целых числа N и K, общее количество ступенек в лестнице и количество разрушенных ступенек (2 <= N <= 106, 0 <= K <= N-2). Далее считывается K целых чисел, номера разрушенных ступенек (в диапазоне от 2 до N-2).

Программа stairs выводит на экран (стандартное устройства вывода) единственное число – максимальное количество ступенек, которые можно разрушить, не выводя лестницу из строя.

Пример входных и выходных данных:

Ввод

Вывод

8 2

6 3

2


 


© Всеукраїнський віртуальний центр олімпіад школярів "ОЛІМП"