Саша та Вася почали займатись чечіткою. Цей танець полягає у притопуванні ногою по підлозі. Але так як вони дуже швидко вчаться, вони вирішили поексперементувати з хореографією.

Хореографія чечітки описується послідовністю з двох букв L та R. L позначає притопування лівою ногою, а R, відповідно, правою. Саша зрозумів, що найкраща частина цього танцю це та, у якій не використовується одна і та ж нога підряд. Він визначив значення хореографії як найбільшу неперервну послідовність, у якій немає двох одинакових послідовних символів.

Як відомо, створення красивого танцю - дуже непростий процес, з безліччю маленьких змін, до того як оптимальний варіант буде знайдено. Тому Вася хочет знати значення хореографії після кожної зміни. Зміна - це заміна L на R (або навпаки) у якійсь позиції.

До усіх змін послідовність складається лише з одних букв L.

Вхідні дані

У першому рядку задано два цілих числа: довжина хореографії n (1 ≤ n ≤ 200000) та кількість змін q (1 ≤ q ≤ 200000). Наступні q рядків містять по одному числу, яке визначає у якій позиції відбувається заміна.

Вихідні дані

Ви повинні вивести q чисел, по одному у кожному рядку: значення хореографії після кожної зміни.