Лестница (stairs)
Как известно, Школа чародейства и волшебства в Хогвардсе имеет 142 лестницы, одна из которых имеет ровноN ступенек. Именно по этой лестнице можно передвигаться, переходя с одной ступеньки на следующую, перепрыгивая через ступеньку или перепрыгивая через две ступеньки, однако перепрыгивать через ступеньки два раза подряд нельзя. Часть ступенек была разрушена в одной из схваток с Волан де Мортом, однако лестницей все еще можно пользоваться, обязательно начиная движение с первой ступеньки и заканчивая на последней.
Альбус Дамблдор не на шутку обеспокоен состоянием этой лестницы и его интересует ответ на такой вопрос: при разрушении какого максимального количества ступенек по лестнице все еще можно будет подняться спервой ступеньки на последнюю.
Формат ввода-вывода:
Программа stairs читает с клавиатуры (стандартного устройства ввода) два целых числа N и K, общее количество ступенек в лестнице и количество разрушенных ступенек (2 <= N <= 106, 0 <= K <= N-2). Далее считывается K целых чисел, номера разрушенных ступенек (в диапазоне от 2 до N-2).
Программа stairs выводит на экран (стандартное устройства вывода) единственное число – максимальное количество ступенек, которые можно разрушить, не выводя лестницу из строя.
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
8 2 6 3 |
2 |