Задача I. Объединения
Задачу добавил: alef
Успешно сдано решений: 21
День близился к закату, и Кондрат решил возвращаться к тому месту, где расстался с Рагнаром. Обратный путь, к его удивлению, занял у него совсем немного времени. Еще издали он заметил, что на скамейке сидят несколько человек. Подойдя поближе, Кондрат увидел, что они наблюдают за художником, расположившимся под раскидистым деревом. Художник рисовал престранную картину. На холсте была изображена полоса, состоящая из N квадратов. Часть квадратов была покрашена черным цветом, часть — белым.
Художник задумчиво смотрел на холст, и время от времени перекрашивал какой-либо из квадратов в противоположный цвет, меняя белый на черный или черный на белый. Зрители пояснили Кондрату, что это известный художник–абстракционист, специализирующийся на клеточной живописи, и сейчас он рисует зебру.
У одного из зрителей Кондрат заметил листок с числами: как оказалось, это номера квадратов в той последовательности, в которой художник их перекрашивал (изначально все квадраты были белыми). Оказалось, что жители зазеркального города не только ценят абстрактную клеточную живопись, но и любят наблюдать за тем, как рождается картина. Для тех же, кто не имеет возможность следить за процессом рисования, потом изготавливается своего рода «фильм» по сделанным записям.
В ожидании Рагнара Кондрат стал подсчитывать количество полос у зебры. Разумеется, оно периодически менялось. Ваша задача — определить количество полос у зебры после каждого действия художника.
Формат входного файла input.txt
Первая строка — целые числа N и A (1 ≤ N, A ≤ 105)— количество квадратов на полосе–зебре и количество перекрашиваний, которое совершил художник.
Вторая строка содержит A целых чисел Cj (j = 1, 2, …, A; 1 ≤ Cj ≤ N) — номера квадратов в той последовательности, в которой их перекрашивал художник.
Формат выходного файла output.txt
Первая строка содержит A целых чисел — количества полос, получившихся после каждого перекрашивания.
Пример входного файла — 1
3 3
2 3 1
Пример выходного файла — 1
3 2 1
Пример входного файла — 2
3 4
2 3 1 2
Пример выходного файла — 2
3 2 1 3
Пояснение к примеру 1.
Изначально все квадраты на полосе были белыми. Обозначим эту конфигурацию как 000
Затем художник покрасил квадрат № 2, получил конфигурацию 010 — и у зебры стало 3 полосы (2 белые + 1 черная)
Далее художник покрасил квадрат № 3, получил конфигурацию 011 — и у зебры стало 2 полосы (1 белая + 1 черная)
Наконец, художник покрасил квадрат № 1, получил конфигурацию 111, а у зебры теперь только 1 (черная) полоса.