Задачи
Прыг-скок
Прыг-скок
Страна коней --- это шахматная доска размера \textbf{1}×\textbf{n}, клетки которой пронумерованы от \textbf{1} до \textbf{n} слева направо. В некоторых клетках доски стоят кони, не более одного коня в одной клетке. Первый конь стоит в клетке с номером \textbf{a_1}, второй стоит в клетке с номером \textbf{a_2}, последний конь стоит в клетке с номером \textbf{a_k} --- всего \textbf{k} коней.
Король коней и его брат играют в игру на описанной шахматной доске. Игроки ходят по очереди, король коней ходит первым. За один ход игрок может выбрать любого коня на шахматной доске и переставить его в ближайшую свободную клетку справа от него. Клетка считается свободной, если в ней нет коней. Выигрывает тот игрок, после хода которого хотя бы один конь окажется в клетке с номером \textbf{n}.
Так как король коней ходит первым, он хочет знать сколько у него существует выигрышных ходов. Другими словами, сколько существует таких ходов, сделав которые, можно выиграть независимо от действий противника. Считайте, что оба игрока играют оптимально.
\InputFile
В первой строке входных данных записаны целые числа \textbf{n} и \textbf{k} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^9}, \textbf{1} ≤ \textbf{k} ≤ \textbf{10^6}) --- количество клеток доски и количество коней на ней.
Во второй строке записана строго возрастающая последовательность \textbf{a_1}, \textbf{a_2}, ..., \textbf{a_k} (\textbf{1} ≤ \textbf{a_i} < \textbf{n}, \textbf{a_i} < \textbf{a_\{i+1\}}) --- позиции коней на доске.
Гарантируется, что в клетке номер \textbf{n} не стоит ни один конь.
\OutputFile
В единственную строку выведите единственное целое число --- количество выигрышных ходов из заданной позиции.
Входные данные #1
5 2 1 3
Выходные данные #1
1