Кроки
Саша та Вася почали займатись чечіткою. Цей танець полягає у притопуванні ногою по підлозі. Але так як вони дуже швидко вчаться, вони вирішили поексперементувати з хореографією.
Хореографія чечітки описується послідовністю з двох букв L та R. L позначає притопування лівою ногою, а R, відповідно, правою. Саша зрозумів, що найкраща частина цього танцю це та, у якій не використовується одна і та ж нога підряд. Він визначив значення хореографії як найбільшу неперервну послідовність, у якій немає двох одинакових послідовних символів.
Як відомо, створення красивого танцю - дуже непростий процес, з безліччю маленьких змін, до того як оптимальний варіант буде знайдено. Тому Вася хочет знати значення хореографії після кожної зміни. Зміна - це заміна L на R (або навпаки) у якійсь позиції.
До усіх змін послідовність складається лише з одних букв L.
Вхідні дані
У першому рядку задано два цілих числа: довжина хореографії n (1 ≤ n ≤ 200000) та кількість змін q (1 ≤ q ≤ 200000). Наступні q рядків містять по одному числу, яке визначає у якій позиції відбувається заміна.
Вихідні дані
Ви повинні вивести q чисел, по одному у кожному рядку: значення хореографії після кожної зміни.