시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB54716013430.524%

문제

창영이와 현우는 탭댄스 학원을 다니고 있다. 탭댄스는 밑창에 탭(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

예제 입력 2

6 5
4
1
1
2
6

예제 출력 2

3
3
3
5
6
W3sicHJvYmxlbV9pZCI6IjI4NDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwZWRcdWIzMDRcdWMyYTQiLCJkZXNjcmlwdGlvbiI6IjxwPlx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVkMGVkXHViMzA0XHVjMmE0IFx1ZDU1OVx1YzZkMFx1Yzc0NCBcdWIyZTRcdWIyYzhcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWQwZWRcdWIzMDRcdWMyYTRcdWIyOTQgXHViYzExXHVjYzNkXHVjNWQwIFx1ZDBlZCh0YXApXHVjNzc0XHViNzdjXHViMjk0IFx1YzFlMFx1YmQ5OVx1Yzc3NFx1Yjk3YyBcdWJkOTlcdWM3NzggXHVhZDZjXHViNDUwXHViOTdjIFx1YzJlMFx1YWNlMCBcdWI5YWNcdWI0ZWNcdWFjMTAgXHVjNzg4XHVhYzhjIFx1ZDUwY1x1Yjg1Y1x1YzViNFx1Yjk3YyBcdWNjZDBcdWMxMWMgXHVhY2JkXHVjZjhjXHVkNTVjIFx1YzE4Y1x1YjlhY1x1Yjk3YyBcdWIwYjRcdWJhNzAgXHVjZDk0XHViMjk0IFx1Y2RhNFx1Yzc3NFx1YjJlNC4gXHVjNTRjXHVhY2UwXHViY2Y0XHViMmM4IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YzY0MCBcdWQ2MDRcdWM2YjBcdWIyOTQgXHVjZGE0XHVjNWQwIFx1YzE4Y1x1YzljOFx1Yzc3NCBcdWM3ODhcdWM1YzhcdWFjZTAsIFx1Yzc3NFx1YzgxYyBcdWFkZjhcdWI0ZTRcdWI5Y2NcdWM3NTggXHVjNTQ4XHViYjM0XHViOTdjIFx1YjljY1x1YjRlNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDBlZFx1YjMwNFx1YzJhNFx1Yzc1OCBcdWM1NDhcdWJiMzRcdWIyOTQgTFx1YWNmYyBSXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWMyMThcdWM1ZjRcdWI4NWMgXHViYjE4XHVjMGFjXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIExcdWM3NDAgXHVjNjdjXHVjYWJkIFx1YmMxY1x1Yjg1YywgUlx1Yzc0MCBcdWM2MjRcdWI5NzhcdWNhYmQgXHViYzFjXHViODVjIFx1YmMxNFx1YjJlNVx1Yzc0NCBcdWQwZWRcdWQ1NThcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzQwIFx1YmMxY1x1Yzc0NCBcdWI0NTAgXHViYzg4IFx1YzVmMFx1YzE4ZFx1ZDU3NFx1YzExYyBcdWMwYWNcdWM2YTlcdWQ1NThcdWM5YzAgXHVjNTRhXHVjNzQ0IFx1YjU0YywgXHVkMGVkXHViMzA0XHVjMmE0XHVjNzU4IFx1YzljNFx1YWMwMFx1YWMwMCBcdWIwOThcdWQwYzBcdWIwOWNcdWIyZTRcdWFjZTAgXHVjMGRkXHVhYzAxXHVkNTVjXHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1YjI5NCBcdWM1NDhcdWJiMzRcdWM3NTggXHVjODEwXHVjMjE4XHViOTdjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzgxMFx1YzIxOFx1YjI5NCBMXHVhY2ZjIFJcdWM3NzQgXHViNDUwIFx1YmM4OCBcdWM1ZjBcdWMxOGRcdWQ1NzRcdWMxMWMgXHViMDk4XHVjNjI0XHVjOWMwIFx1YzU0YVx1YjI5NCBcdWM1ZjBcdWMxOGRcdWI0MWMgXHVjNmQwXHVjMThjXHViNGU0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjMDBcdWM3YTUgXHVhZTM0IFx1YmQ4MFx1YmQ4NCBcdWMyMThcdWM1ZjRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM1NDhcdWJiMzRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI5ZTRcdWM2YjAgXHVjNWI0XHViODI0XHVjNmI0IFx1Yzc3Y1x1Yzc3NFx1YjJlNC4gXHVkNjA0XHVjNmIwXHViMjk0IFx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWNkYTRcdWM3NDQgXHViY2Y4IFx1YjRhNCwgXHVjNTQ4XHViYjM0XHVjNWQwXHVjMTFjIFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWJkODBcdWJkODRcdWM3NDQgXHVjNTRjXHViODI0XHVjOGZjXHVjNWM4XHViMmU0LiBcdWNjM2RcdWM2MDFcdWM3NzRcdWIyOTQgXHViOWU0XHViYzg4IFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWI1NGMgXHViOWM4XHViMmU0IFx1YzU0OFx1YmIzNFx1Yzc1OCBcdWM4MTBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzIxOFx1YzgxNVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggTFx1Yzc0NCBSXHViODVjIFx1YjYxMFx1YjI5NCBSXHVjNzQ0IExcdWI4NWMgXHViYzE0XHVhZmI4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWFjMDAgXHViOWNjXHViNGUwIFx1YzU0OFx1YmIzNFx1YzVkMFx1YjI5NCBMXHViOWNjIFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2MzZFx1YzYwMVx1Yzc3NFx1Yzc1OCBcdWM1NDhcdWJiMzRcdWM3NTggXHVhZTM4XHVjNzc0IE4oMSZsZTsgTiAmbGU7IDIwMCwwMDApXHVhY2ZjIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWM1NDhcdWJiMzRcdWI5N2MgXHVjMjE4XHVjODE1XHVkNTVjIFx1ZDY5Zlx1YzIxOCBRKDEmbGU7IFEgJmxlOyAyMDAsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBRXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWQ2MDRcdWM2YjBcdWFjMDAgXHVjNTQ4XHViYjM0XHVjNzU4IFx1YmE4NyBcdWJjODhcdWM5ZjhcdWI5N2MgXHVjMjE4XHVjODE1XHVkNTg4XHViMjk0XHVjOWMwXHVhYzAwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDljXHViODI1XHVjNzQwIFFcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDYwNFx1YzZiMFx1YWMwMCBcdWNjM2RcdWM2MDFcdWM3NzRcdWM3NTggXHVjNTQ4XHViYjM0XHViOTdjIFx1YzIxOFx1YzgxNVx1ZDU2MCBcdWI1NGNcdWI5YzhcdWIyZTQgXHVjNTQ4XHViYjM0XHVjNzU4IFx1YzgxMFx1YzIxOFx1Yjk3YyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIiwic2FtcGxlX2V4cGxhaW5fMSI6IjxwPlx1YzU0OFx1YmIzNFx1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YmNjMFx1ZDU1Y1x1YjJlNC4gTExMTExMICZyYXJyOyBMPHN0cm9uZz5SPFwvc3Ryb25nPkxMTEwgJnJhcnI7IExSTDxzdHJvbmc+UjxcL3N0cm9uZz5MTDxcL3A+XHJcbiJ9LHsicHJvYmxlbV9pZCI6IjI4NDkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJTVEVQIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBhbmQgU2xhdmtvIHN0YXJ0ZWQgdGFraW5nIHRhcCBkYW5jZSBsZXNzb25zLiBUaGlzIGRhbmNlIGNvbnNpc3RzIG1vc3RseSBvZiB0YXBwaW5nIHRoZSBmbG9vciB3aXRoIGEgc3BlY2lhbCBraW5kIG9mIHNob2UuIFNpbmNlIE1pcmtvIGFuZCBTbGF2a28gYXJlIGZhc3QgbGVhcm5lcnMsIHRoZXkgZGVjaWRlZCB0byBjb21lIHVwIHdpdGggdGhlaXIgb3duIGNob3Jlb2dyYXBoeS48XC9wPlxyXG5cclxuPHA+VGFwIGRhbmNlIGNob3Jlb2dyYXBoeSBjYW4gYmUgZGVzY3JpYmVkIGFzIGEgc2VxdWVuY2UgY29uc2lzdGluZyBvZiB0d28gbGV0dGVycywgJmxzcXVvO0wmcnNxdW87IGFuZCAmbHNxdW87UiZyc3F1bzsuICZsc3F1bztMJnJzcXVvOyBtZWFucyB0aGF0IHlvdSBzaG91bGQgdGFwIHRoZSBmbG9vciB3aXRoIHlvdXIgbGVmdCBmb290LCBhbmQgJmxzcXVvO1ImcnNxdW87IHdpdGggeW91ciByaWdodCBmb290LiBNaXJrbyByZWFsaXNlZCB0aGF0IHRoZSBtb3N0IGV4Y2l0aW5nIHBhcnRzIG9mIHRhcCBkYW5jaW5nIGFyZSB0aGUgb25lcyBpbiB3aGljaCB5b3UgZG9uJnJzcXVvO3QgdXNlIHRoZSBzYW1lIGxlZyB0d2ljZSBpbiBhIHJvdy4gSGUgZGVmaW5lZCB0aGUgdmFsdWUgb2YgYSBjaG9yZW9ncmFwaHkgYXMgdGhlIGxvbmdlc3Qgc3Vic2VxdWVuY2Ugb2YgY29uc2VjdXRpdmUgZWxlbWVudHMgdGhhdCBkb2VzbiZyc3F1bzt0IGNvbnRhaW4gdHdvIGNvbnNlY3V0aXZlICZsc3F1bztMJnJzcXVvO3Mgb3IgJmxzcXVvO1ImcnNxdW87cy48XC9wPlxyXG5cclxuPHA+QXMgd2UgYWxsIGtub3csIGRlc2lnbmluZyBhIGNob3Jlb2dyYXBoeSBjYW4gYmUgdmVyeSBjaGFsbGVuZ2luZywgd2l0aCBsb3RzIG9mIHNtYWxsIGNoYW5nZXMgdW50aWwgaXQmcnNxdW87cyBkb25lLiBGb3IgZXZlcnkgYWx0ZXJhdGlvbiB0aGF0IFNsYXZrbyBkb2VzLCBoZSB3b3VsZCBsaWtlIHRvIGtub3cgdGhlIGN1cnJlbnQgY2hvcmVvZ3JhcGh5IHZhbHVlLiBPbmUgYWx0ZXJhdGlvbiBpcyBjaGFuZ2luZyBvbmUgJmxzcXVvO0wmcnNxdW87IHRvICZsc3F1bztSJnJzcXVvOywgYW5kIHZpY2UgdmVyc2EuPFwvcD5cclxuXHJcbjxwPkJlZm9yZSBhbnkgYWx0ZXJhdGlvbnMgYXJlIG1hZGUsIHRoZSBjaG9yZW9ncmFwaHkgY29uc2lzdHMgb25seSBvZiBsZXR0ZXJzICZsc3F1bztMJnJzcXVvOy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHR3byBpbnRlZ2VycywgdGhlIGNob3Jlb2dyYXBoeSBsZW5ndGggTiAoMSAmbGU7IE4gJmxlOyAyMDAgMDAwKSwgYW5kIHRoZSBudW1iZXIgb2YgYWx0ZXJhdGlvbnMgUSAoMSAmbGU7IFEgJmxlOyAyMDAgMDAwKS48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBRIGxpbmVzIGNvbnRhaW5zIGFuIGludGVnZXIgc3BlY2lmeWluZyB0aGUgcG9zaXRpb24gdGhhdCBNaXJrbyBhbmQgU2xhdmtvIGFyZSBhbHRlcmluZywgaW4gb3JkZXIgb2YgYWx0ZXJhdGlvbi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IG11c3QgY29udGFpbiBRIGludGVnZXJzLCBvbmUgcGVyIGxpbmUgLSB0aGUgY3VycmVudCB2YWx1ZXMgb2YgdGhlIGNob3Jlb2dyYXBoeSBhZnRlciBlYWNoIGFsdGVyYXRpb24uPFwvcD5cclxuIiwiaGludCI6IjxwPkNob3Jlb2dyYXBoaWVzIGFyZTogTExMTExMICZyYXJyOyZuYnNwO0xSTExMTCAmcmFycjsmbmJzcDtMUkxSTEw8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2giLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHA+Q2hvcmVvZ3JhcGhpZXMgYXJlOiBMTExMTEwgJnJhcnI7IEw8c3Ryb25nPlI8XC9zdHJvbmc+TExMTCAmcmFycjsgTFJMPHN0cm9uZz5SPFwvc3Ryb25nPkxMPFwvcD5cclxuIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #6 5번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 번역을 찾은 사람: Green55