Задача E. Покраска забора ≡

Условие

Сегодня Евгений решил заняться покраской забора вокруг своего дома. Забор деревянный и состоит из N досок, причем каждая из них имеет ровно две соседние доски: 1 и N доска являются соседними.

Для того, чтобы покраска не стала рутинным занятием, Евгений решил красить доски не по порядку. За сегодня он планирует покрасить лишь Q досок, i-й из которых будет покрашена a_i доска.

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

Требуется написать программу, которая по действиям Евгения определит количество непокрашенных участков после покраски очередной доски.

Формат входных данных

Первая строка содержит два целых числа N и Q — количество досок в заборе и количество досок, которые Евгений собирается покрасить, соответственно.

Вторая строка содержит Q различных целых чисел a_i — номер доски, которую Евгений будет красить i-й по счету.

Формат выходных данных

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

Ограничения

1 ≤ N ≤ 10⁹,

1 ≤ Q ≤ min(N, 10⁵)

1 ≤ a_i ≤ N

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснения к примерам

В первом примере после покраски 2 доски получится один непрерывных участок (3, 4, 1), после покраски 4 доски — два участка (1) и (3), после покраски 3 — (1), а после покраски 1 — не покрашенных досок не останется.

Примеры тестов

4 4
2 4 3 1

1 2 1 0

8 6
2 4 7 1 3 8

1 2 3 3 2 1

10 10
2 7 1 9 3 10 5 6 8 4

1 2 2 3 3 2 3 2 1 0