시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 151 31 27 29.348%

문제

창영이와 현우는 탭댄스 학원을 다니고 있다. 탭댄스는 밑창에 탭(tap)이라는 쇠붙이를 붙인 구두를 신고 리듬감 있게 플로어를 쳐서 경쾌한 소리를 내며 추는 춤이다. 알고보니 창영이와 현우는 춤에 소질이 있었고, 이제 그들만의 안무를 만드려고 한다.

탭댄스의 안무는 L과 R로 이루어진 수열로 묘사할 수 있다. L은 왼쪽 발로, R은 오른쪽 발로 바닥을 탭하는 것이다. 창영이는 같은 발을 두 번 연속해서 사용하지 않을 때, 탭댄스의 진가가 나타난다고 생각한다. 따라서, 창영이는 안무의 점수를 만들었다. 안무의 점수는 L이나 R이 두 번 연속해서 나오지 않는 가장 긴 부분 수열의 길이이다.

안무를 만드는 것은 매우 어려운 일이다. 현우는 창영이의 춤을 본 뒤, 안무에서 수정할 부분을 알려주었다. 창영이는 매번 수정할 때 마다 안무의 점수를 구하려고 한다. 안무의 수정은 하나의 L을 R로 또는 R을 L로 바꾸는 것이다.

가장 처음에 창영이가 만든 안무에는 L만 포함하고 있다.

입력

첫째 줄에 창영이의 안무의 길이 N(1≤ N ≤ 200,000)과 현우가 안무를 수정한 횟수 Q(1≤ Q ≤ 200,000)가 주어진다.

다음 Q개 줄에는 현우가 안무의 몇 번째를 수정했는지가 순서대로 주어진다.

출력

출력은 Q개의 정수로 이루어져 있다. 현우가 창영이의 안무를 수정할 때마다 안무의 점수를 한 줄에 하나씩 출력한다.

예제 입력 1

6 2
2
4

예제 출력 1

3
5

힌트

안무는 다음과 같이 변한다. LLLLLL -> LRLLLL -> LRLRLL

W3sicHJvYmxlbV9pZCI6IjI4NDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwZWRcdWIzMDRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVkMGVkXHViMzA0XHVjMmE0IFx1ZDU1OVx1YzZkMFx1Yzc0NCBcdWIyZTRcdWIyYzhcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQwZWRcdWIzMDRcdWMyYTRcdWIyOTQgXHViYzExXHVjYzNkXHVjNWQwIFx1ZDBlZCh0YXApXHVjNzc0XHViNzdjXHViMjk0IFx1YzFlMFx1YmQ5OVx1Yzc3NFx1Yjk3YyBcdWJkOTlcdWM3NzggXHVhZDZjXHViNDUwXHViOTdjIFx1YzJlMFx1YWNlMCBcdWI5YWNcdWI0ZWNcdWFjMTAgXHVjNzg4XHVhYzhjIFx1ZDUwY1x1Yjg1Y1x1YzViNFx1Yjk3YyBcdWNjZDBcdWMxMWMgXHVhY2JkXHVjZjhjXHVkNTVjIFx1YzE4Y1x1YjlhY1x1Yjk3YyBcdWIwYjRcdWJhNzAgXHVjZDk0XHViMjk0IFx1Y2RhNFx1Yzc3NFx1YjJlNC4gXHVjNTRjXHVhY2UwXHViY2Y0XHViMmM4IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjZGE0XHVjNWQwIFx1YzE4Y1x1YzljOFx1Yzc3NCBcdWM3ODhcdWM1YzhcdWFjZTAsIFx1Yzc3NFx1YzgxYyBcdWFkZjhcdWI0ZTRcdWI5Y2NcdWM3NTggXHVjNTQ4XHViYjM0XHViOTdjIFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDBlZFx1YjMwNFx1YzJhNFx1Yzc1OCBcdWM1NDhcdWJiMzRcdWIyOTQgTFx1YWNmYyBSXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViYjE4XHVjMGFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIExcdWM3NDAgXHVjNjdjXHVjYWJkIFx1YmMxY1x1Yjg1YywgUlx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViYzFjXHViODVjIFx1YmMxNFx1YjJlNVx1Yzc0NCBcdWQwZWRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YmMxY1x1Yzc0NCBcdWI0NTAgXHViYzg4IFx1YzVmMFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0YywgXHVkMGVkXHViMzA0XHVjMmE0XHVjNzU4IFx1YzljNFx1YWMwMFx1YWMwMCBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM1NDhcdWJiMzRcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCBMXHVjNzc0XHViMDk4IFJcdWM3NzQgXHViNDUwIFx1YmM4OCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM1NDhcdWJiMzRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNWI0XHViODI0XHVjNmI0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWNkYTRcdWM3NDQgXHViY2Y4IFx1YjRhNCwgXHVjNTQ4XHViYjM0XHVjNWQwXHVjMTFjIFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWJkODBcdWJkODRcdWM3NDQgXHVjNTRjXHViODI0XHVjOGZjXHVjNWM4XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHViYzg4IFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YzU0OFx1YmIzNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzIxOFx1YzgxNVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggTFx1Yzc0NCBSXHViODVjIFx1YjYxMFx1YjI5NCBSXHVjNzQ0IExcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YzU0OFx1YmIzNFx1YzVkMFx1YjI5NCBMXHViOWNjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWM1NDhcdWJiMzRcdWM3NTggXHVhZTM4XHVjNzc0IE4oMSZsZTsgTiAmbGU7IDIwMCwwMDApXHVhY2ZjIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWM1NDhcdWJiMzRcdWI5N2MgXHVjMjE4XHVjODE1XHVkNTVjIFx1ZDY5Zlx1YzIxOCBRKDEmbGU7IFEgJmxlOyAyMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBRXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVjNTQ4XHViYjM0XHVjNzU4IFx1YmE4NyBcdWJjODhcdWM5ZjhcdWI5N2MgXHVjMjE4XHVjODE1XHVkNTg4XHViMjk0XHVjOWMwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjZDljXHViODI1XHVjNzQwIFFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWM3NTggXHVjNTQ4XHViYjM0XHViOTdjIFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlxyXG5cdFx1YzU0OFx1YmIzNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1Y1x1YjJlNC4gTExMTExMIC0mZ3Q7IExSTExMTCAtJmd0OyBMUkxSTEw8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVEVQIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIHN0YXJ0ZWQgdGFraW5nIHRhcCBkYW5jZSBsZXNzb25zLiBUaGlzIGRhbmNlIGNvbnNpc3RzIG1vc3RseSBvZiB0YXBwaW5nIHRoZSBmbG9vciB3aXRoIGEgc3BlY2lhbCBraW5kIG9mIHNob2UuIFNpbmNlIE1pcmtvIGFuZCBTbGF2a28gYXJlIGZhc3QgbGVhcm5lcnMsIHRoZXkgZGVjaWRlZCB0byBjb21lIHVwIHdpdGggdGhlaXIgb3duIGNob3Jlb2dyYXBoeS48XC9wPlxyXG5cclxuPHA+VGFwIGRhbmNlIGNob3Jlb2dyYXBoeSBjYW4gYmUgZGVzY3JpYmVkIGFzIGEgc2VxdWVuY2UgY29uc2lzdGluZyBvZiB0d28gbGV0dGVycywgJmxzcXVvO0wmcnNxdW87IGFuZCAmbHNxdW87UiZyc3F1bzsuICZsc3F1bztMJnJzcXVvOyBtZWFucyB0aGF0IHlvdSBzaG91bGQgdGFwIHRoZSBmbG9vciB3aXRoIHlvdXIgbGVmdCBmb290LCBhbmQgJmxzcXVvO1ImcnNxdW87IHdpdGggeW91ciByaWdodCBmb290LiBNaXJrbyByZWFsaXNlZCB0aGF0IHRoZSBtb3N0IGV4Y2l0aW5nIHBhcnRzIG9mIHRhcCBkYW5jaW5nIGFyZSB0aGUgb25lcyBpbiB3aGljaCB5b3UgZG9uJnJzcXVvO3QgdXNlIHRoZSBzYW1lIGxlZyB0d2ljZSBpbiBhIHJvdy4gSGUgZGVmaW5lZCB0aGUgdmFsdWUgb2YgYSBjaG9yZW9ncmFwaHkgYXMgdGhlIGxvbmdlc3Qgc3Vic2VxdWVuY2Ugb2YgY29uc2VjdXRpdmUgZWxlbWVudHMgdGhhdCBkb2VzbiZyc3F1bzt0IGNvbnRhaW4gdHdvIGNvbnNlY3V0aXZlICZsc3F1bztMJnJzcXVvO3Mgb3IgJmxzcXVvO1ImcnNxdW87cy48XC9wPlxyXG5cclxuPHA+QXMgd2UgYWxsIGtub3csIGRlc2lnbmluZyBhIGNob3Jlb2dyYXBoeSBjYW4gYmUgdmVyeSBjaGFsbGVuZ2luZywgd2l0aCBsb3RzIG9mIHNtYWxsIGNoYW5nZXMgdW50aWwgaXQmcnNxdW87cyBkb25lLiBGb3IgZXZlcnkgYWx0ZXJhdGlvbiB0aGF0IFNsYXZrbyBkb2VzLCBoZSB3b3VsZCBsaWtlIHRvIGtub3cgdGhlIGN1cnJlbnQgY2hvcmVvZ3JhcGh5IHZhbHVlLiBPbmUgYWx0ZXJhdGlvbiBpcyBjaGFuZ2luZyBvbmUgJmxzcXVvO0wmcnNxdW87IHRvICZsc3F1bztSJnJzcXVvOywgYW5kIHZpY2UgdmVyc2EuPFwvcD5cclxuXHJcbjxwPkJlZm9yZSBhbnkgYWx0ZXJhdGlvbnMgYXJlIG1hZGUsIHRoZSBjaG9yZW9ncmFwaHkgY29uc2lzdHMgb25seSBvZiBsZXR0ZXJzICZsc3F1bztMJnJzcXVvOy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIGNob3Jlb2dyYXBoeSBsZW5ndGggTiAoMSAmbGU7IE4gJmxlOyAyMDAgMDAwKSwgYW5kIHRoZSBudW1iZXIgb2YgYWx0ZXJhdGlvbnMgUSAoMSAmbGU7IFEgJmxlOyAyMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBRIGxpbmVzIGNvbnRhaW5zIGFuIGludGVnZXIgc3BlY2lmeWluZyB0aGUgcG9zaXRpb24gdGhhdCBNaXJrbyBhbmQgU2xhdmtvIGFyZSBhbHRlcmluZywgaW4gb3JkZXIgb2YgYWx0ZXJhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IG11c3QgY29udGFpbiBRIGludGVnZXJzLCBvbmUgcGVyIGxpbmUgLSB0aGUgY3VycmVudCB2YWx1ZXMgb2YgdGhlIGNob3Jlb2dyYXBoeSBhZnRlciBlYWNoIGFsdGVyYXRpb24uPFwvcD5cclxuIiwiaGludCI6IjxwPkNob3Jlb2dyYXBoaWVzIGFyZTogTExMTExMICZyYXJyOyZuYnNwO0xSTExMTCAmcmFycjsmbmJzcDtMUkxSTEw8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==