32033번 - 민들레

문제

동서로 무한히 길게 뻗은 UCPC 도로에 1의 간격으로 무한히 많은 화분을 놓아 민들레 화단을 만들었다. 모든 화분에는 정수 번호가 매겨져 있는데, 0번 화분을 기준으로 동쪽으로 k만큼 떨어진 화분의 번호는 k번, 서쪽으로 k만큼 떨어진 화분의 번호는 −k번이다. 각 화분에는 최대 한 송이의 민들레만 자랄 수 있다.

민들레는 바람이 불면 그 방향으로 1만큼 떨어진 화분에 홀씨를 날린다. 심거나 바람에 날려 화분에 떨어진 민들레 씨는 그 화분에 다른 민들레가 없으면 빠르게 자라나 다음 날이면 홀씨를 날릴 수 있게 된다. 각 민들레마다 홀씨는 충분히 많아 다 떨어지는 일은 없다.

시우는 로봇을 이용해 N일에 걸쳐 민들레 화단을 관찰하려 한다. 로봇은 화단을 관찰하는 동안 매일 하루에 하나씩 명령을 입력받아 수행한다. 로봇이 수행할 수 있는 명령의 종류는 다음과 같다.

• L: 서쪽으로 바람을 일으킨다. 모든 정수 x에 대해, x번 화분에 민들레가 심겨 있고 (x − 1)번 화분에 민들레가 없다면 다음 날 (x − 1)번 화분에 새 민들레가 자란다.
• R: 동쪽으로 바람을 일으킨다. 모든 정수 x에 대해, x번 화분에 민들레가 심겨 있고 (x + 1)번 화분에 민들레가 없다면 다음 날 (x + 1)번 화분에 새 민들레가 자란다.
• C x: x번 화분에 민들레 씨를 심는다. x번 화분에 민들레가 없다면 다음 날 새 민들레가 자란다. (−10⁹ ≤ x ≤ 10⁹; x는 정수)
• Q: 현재 민들레가 있는 화분의 개수를 기록한다.

화단 관찰을 시작하기 전에는 0번 화분에만 민들레 한 송이가 심겨 있다. 시우가 N일 동안 로봇에게 요청한 명령의 목록이 주어졌을 때, 명령를 수행하는 프로그램을 작성하시오.

입력

첫 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 200 000)

둘째 줄부터 N개의 줄에 걸쳐 한 줄에 하나씩 명령이 주어진다. 그중 i번째 명령은 로봇이 i일에 처리해야 하는 명령을 의미한다. (1 ≤ i ≤ N)

명령 중 Q는 하나 이상 있다.

출력

명령으로 Q가 주어진 날마다, 그날 민들레가 있는 화분의 개수를 한 줄에 하나씩 시간순으로 출력한다.

제한

힌트