Шаги
Саша и Вася начали заниматься чечеткой. Этот танец состоит из притопывания ногой по полу. Но так как они очень быстро учатся, они решили поэксперементировать с хореографией.
Хореография чечетки описывается последовательностью из двух букв L и R. L означает притопывание левой ногой, а R, соотвественно, правой. Саша понял, что самая лучшая часть этого танца это та, в которой не используется одна и та же нога подряд. Он определил значение хореографии как наибольшую непрерывную последовательность, в которой нет двух одинаковых последовательных символов.
Как известно, создание красивого танца - очень непростой процесс, с множеством маленьких изменений, прежде чем оптимальный вариант будет найден. Поэтому Вася хочет знать значение хореографии после каждого изменения. Изменение - это замена L на R (или наоборот) в какой-то позиции.
До всех изменений последовательность состоит только из одних букв L.
Входные данные
В первой строке задано два целых числа: длина хореографии n (1 ≤ n ≤ 200000) и число изменений q (1 ≤ q ≤ 200000). Следующие q строк содержат по одному числу, определяющего в какой позиции происходит замена.
Выходные данные
Вы должны вывести q чисел, по одному на каждой строке: значения хореографии после каждого изменения.