뒤집는 우편물 받침대

문제

우체국의 분류 작업대에는 우편물을 한 줄로 놓는 긴 받침대가 있다. 받침대에 놓인 우편물에는 식별 번호가 적혀 있다. 번호가 같은 우편물이 여러 개 있을 수 있으며, 그런 우편물도 각각 별개의 물건으로 취급한다. 작업을 시작할 때 받침대는 비어 있고, 이후 기록된 명령을 위에서부터 차례대로 수행한다. 받침대에 놓인 우편물의 순서에는 앞과 뒤가 있다. 새 우편물을 올리는 명령은 A x로 기록한다. 이 명령을 수행하면 식별 번호가 x인 우편물 하나를 현재 순서의 맨 뒤에 추가한다. 받침대가 비어 있다면 그 우편물이 유일한 우편물이 된다. 새 우편물을 추가하는 것만으로 기존 우편물 사이의 순서가 바뀌지는 않는다. 받침대를 돌리는 명령은 R로 기록한다. 이 명령을 수행하면 현재 놓인 모든 우편물의 순서가 반대가 된다. 맨 앞의 우편물은 맨 뒤로 가고, 맨 뒤의 우편물은 맨 앞으로 온다. 빈 받침대나 우편물이 하나뿐인 받침대를 돌려도 명령은 정상적으로 수행된다. 회전 이후에 들어오는 새 우편물은 회전한 결과의 순서를 기준으로 맨 뒤에 추가한다. 발송 명령은 D로 기록한다. 받침대에 우편물이 있으면 현재 맨 앞의 우편물 하나를 꺼내고 그 식별 번호를 기록한다. 우편물이 없으면 아무것도 꺼내지 않고 0을 기록한다. 꺼낸 우편물은 받침대에 다시 나타나지 않는다. 발송으로 남은 우편물의 상대적인 순서가 바뀌지는 않는다. 명령 기록이 주어질 때, 모든 발송 명령에서 기록할 번호를 순서대로 구하는 프로그램을 작성한다. 마지막에는 모든 명령을 수행한 직후 받침대에 남은 우편물의 개수도 출력해야 한다. 받침대의 길이는 충분히 길어 우편물을 추가하지 못하는 경우는 없다.

입력

첫째 줄에 명령 수를 나타내는 정수 Q가 주어진다.
다음 Q개 줄에 각각 A x, R, D 중 하나의 명령이 주어진다.
1 ≤ Q ≤ 30,000이며, A 명령의 x는 1 ≤ x ≤ 999,999인 정수이다. A 명령이나 D 명령이 하나도 없는 입력도 가능하다.

출력

D 명령마다 기록한 번호를 명령 순서대로 한 줄에 하나씩 출력한다. 모든 D 명령의 출력 뒤에, 최종적으로 남은 우편물의 개수를 별도의 한 줄에 출력한다. D 명령이 없으면 최종 개수만 출력한다.

9
A 42
A 17
R
A 88
D
R
D
D
D

17
88
42
0
0

4
R
A 5
A 5
R

2

3
D
R
D

0
0
0

출처: Devin.KR 자체 제작