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

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 109,

1 ≤ Q ≤ min(N, 105)

1 ≤ ai ≤ N

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

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

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

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
NQ
1 21 1 ≤ N ≤ 102 1 ≤ Q ≤ min(N, 102)
2 25 1 ≤ N ≤ 105 1 ≤ Q ≤ min(N, 103) 1
3 31 1 ≤ N ≤ 105 1 ≤ Q ≤ min(N, 105) 1-2
4 23 1 ≤ N ≤ 109 1 ≤ Q ≤ min(N, 105) 1-3

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

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

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

Стандартный вход Стандартный выход
1
4 4
2 4 3 1
1 2 1 0
2
8 6
2 4 7 1 3 8
1 2 3 3 2 1
3
10 10
2 7 1 9 3 10 5 6 8 4
1 2 2 3 3 2 3 2 1 0

0.286s 0.033s 15