출발 대기 구역의 두 문

문제

한 마라톤 대회에서는 출발 시각이 가까워진 참가자를 긴 대기 구역에 한 줄로 세운다. 대기 구역에는 왼쪽 문과 오른쪽 문이 하나씩 있으며, 두 문 모두 입장과 출발에 사용할 수 있다. 운영 요원은 무전으로 전달되는 기록을 순서대로 처리하여 참가자를 들여보내거나 출발시킨다. 처음에는 대기 구역이 비어 있다. 대기 구역에 새로 입장하는 참가자에게는 입장 순서대로 1번부터 연속된 정수 번호를 부여한다. 어느 문으로 입장하더라도 같은 번호 순서를 사용한다. 이미 출발한 참가자는 다시 입장하지 않으며, 한 번 사용한 번호도 다시 부여하지 않는다. 따라서 지금까지 입장한 참가자가 k명이면 다음 입장자의 번호는 k+1이다. 기록은 네 종류다. L은 새 참가자 한 명을 왼쪽 문으로 입장시켜 현재 줄의 맨 왼쪽에 세우는 기록이다. R은 새 참가자 한 명을 오른쪽 문으로 입장시켜 맨 오른쪽에 세우는 기록이다. F는 현재 맨 왼쪽 참가자 한 명을 출발시키는 기록이고, B는 현재 맨 오른쪽 참가자 한 명을 출발시키는 기록이다. 입장하거나 출발할 때 나머지 참가자의 상대적인 순서는 바뀌지 않는다. 출발 기록을 처리할 때 대기 구역이 비어 있다면 아무도 출발하지 않는다. 이 경우도 출발 요청 한 번으로 세며, 그 요청의 결과는 -1로 기록한다. 참가자가 한 명만 있다면 어느 문에서 출발을 요청해도 그 참가자가 출발한다. 모든 기록은 주어진 순서대로 하나씩 완료되므로 동시에 처리하거나 동점을 판단할 일은 없다. 운영 기록을 바탕으로 각 출발 요청에서 출발한 참가자의 번호를 구한다. 모든 기록을 처리한 뒤에는 아직 대기 구역에 남아 있는 참가자 수도 함께 구한다. 출발 요청이 한 번도 없더라도 마지막 참가자 수는 반드시 출력한다.

입력

첫째 줄에 기록의 개수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
다음 N개 줄에는 각 기록을 나타내는 문자 L, R, F, B 중 하나가 한 줄에 하나씩 주어진다. 각 문자의 의미는 지문과 같다. 입장자의 번호는 입력으로 주어지지 않고 입장 순서에 따라 결정된다.

출력

F 또는 B 기록이 나타날 때마다 출발한 참가자의 번호를 한 줄에 출력한다. 해당 기록을 처리하기 직전에 대기 구역이 비어 있었다면 -1을 출력한다. 모든 기록을 처리한 뒤에는 남아 있는 참가자 수를 마지막 줄에 출력한다. 출발 기록의 개수를 K라고 할 때 출력은 정확히 K+1줄이다.

10
L
R
L
F
B
R
L
B
F
F

3
2
4
5
1
0

5
F
B
R
B
F

-1
-1
1
-1
0

4
R
L
L
R

4

출처: Devin.KR 자체 제작