Стриб-скок#4655
У Країні Коней грають на шахівниці розміром 1 \times n, де клітинки пронумеровано послідовно від до , зліва направо. В деяких з цих клітинок стоять коні, причому в кожній клітинці може бути не більше одного коня. Перший кінь стоїть у клітинці a_1, другий у a_2, а останній у a_k, всього коней.
Король Коней та його брат по черзі грають у цю гру на дошці. Хід робить спочатку Король Коней. На кожному ході гравець може вибрати будь-якого коня на дошці й пересунути його на найближчу вільну клітинку праворуч. Клітинка вважається вільною, якщо в ній немає коня. Той, хто першим пересуне будь-якого коня у клітинку номер , перемагає гру.
Оскільки Король Коней ходить першим, він хоче дізнатися, скільки переможних ходів у нього є. Іншими словами, скільки ходів він може зробити так, щоб, незалежно від гри суперника, він міг гарантувати перемогу, якщо обидва гратимуть оптимально.
У першому рядку задано числа та (1 \leq n \leq 10^9, 1 \leq k \leq 10^6) — кількість клітинок на дошці та кількість коней.
У другому рядку задано строго зростаючу послідовність a_1, a_2, \ldots, a_k (1 \leq a_i < n, a_i < a_{i+1}) — позиції коней.
Гарантується, що в клітинці немає коня.
Виведіть одне ціле число — кількість переможних ходів з даної позиції.
Приклад 1