eolymp
bolt
Try our new interface for solving problems
Məsələlər

Прыг-скок

Прыг-скок

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

Страна коней — это шахматная доска размера 1×n, клетки которой пронумерованы от 1 до n слева направо. В некоторых клетках доски стоят кони, не более одного коня в одной клетке. Первый конь стоит в клетке с номером a_1, второй стоит в клетке с номером a_2, последний конь стоит в клетке с номером a_k — всего k коней.

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

Так как король коней ходит первым, он хочет знать сколько у него существует выигрышных ходов. Другими словами, сколько существует таких ходов, сделав которые, можно выиграть независимо от действий противника. Считайте, что оба игрока играют оптимально.

Giriş verilənləri

В первой строке входных данных записаны целые числа n и k (1n10^9, 1k10^6) — количество клеток доски и количество коней на ней.

Во второй строке записана строго возрастающая последовательность a_1, a_2, ..., a_k (1a_i < n, a_i < a_{i+1}) — позиции коней на доске.

Гарантируется, что в клетке номер n не стоит ни один конь.

Çıxış verilənləri

В единственную строку выведите единственное целое число — количество выигрышных ходов из заданной позиции.

Nümunə

Giriş verilənləri #1
5 2
1 3
Çıxış verilənləri #1
1
Mənbə Winter School Kharkov 2013, Day 6 - G.Agapov and I.Fefer