시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 547 | 160 | 134 | 30.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개의 정수로 이루어져 있다. 현우가 창영이의 안무를 수정할 때마다 안무의 점수를 한 줄에 하나씩 출력한다.
6 2 2 4
3 5
안무는 다음과 같이 변한다. LLLLLL → LRLLLL → LRLRLL
6 5 4 1 1 2 6
3 3 3 5 6