양쪽에서 정리하는 항공권

문제

작은 공항의 탑승구에서는 종이 항공권을 한 줄로 놓고 탑승 순서를 관리한다. 항공권마다 서로 다른 양의 정수 번호가 적혀 있다. 직원이 바라보는 줄에는 앞과 뒤가 있으며, 처음에는 항공권이 한 장도 없다. 직원은 업무 기록에 적힌 명령을 위에서부터 차례대로 실행한다. 명령 L x는 번호 x인 새 항공권을 현재 줄의 맨 앞에 넣는다. 명령 R x는 번호 x인 새 항공권을 현재 줄의 맨 뒤에 넣는다. 새로 넣는 항공권의 번호는 이전에 한 번이라도 넣었던 모든 항공권의 번호와 다르다. 이미 탑승 처리되어 줄에서 사라진 항공권의 번호도 다시 사용하지 않는다. 명령 B는 현재 맨 앞에 있는 항공권 한 장을 꺼내 탑승 처리하고, 그 항공권의 번호를 기록한다. 줄이 비어 있으면 아무 항공권도 꺼내지 않고 -1을 기록한다. 명령 T는 줄 전체의 순서를 뒤집는다. 뒤집기 직전 맨 뒤의 항공권이 새 맨 앞이 되고, 나머지 항공권들의 순서도 모두 반대가 된다. 항공권이 없거나 한 장뿐인 경우에도 T를 실행할 수 있으며, 이때 보이는 줄의 순서는 달라지지 않는다. L과 R에서 말하는 앞과 뒤는 항상 해당 명령을 실행하는 순간의 줄을 기준으로 한다. 따라서 T 이후에 들어온 새 항공권도 뒤집힌 줄의 현재 앞이나 뒤에 놓인다. 업무 기록에 등장하는 모든 B 명령의 기록값을 순서대로 구한다. 마지막 명령까지 처리한 후 줄에 남은 항공권의 수 역시 함께 구해야 한다. 번호의 크기 자체는 탑승 순서에 영향을 주지 않는다.

입력

첫째 줄에 명령 수인 정수 Q가 주어진다. 1≤Q≤20,000이다. 다음 Q개 줄에 L x, R x, B, T 중 하나가 주어진다. x는 1 이상 100,000 이하의 정수이며, 모든 삽입 명령에서 서로 다르다. B 명령이 없을 수도 있다.

출력

각 B 명령의 기록값을 명령 순서대로 한 줄에 하나씩 출력한다. 그 뒤 마지막 줄에 남은 항공권의 수를 출력한다. B 명령이 없다면 남은 항공권의 수만 출력한다.

9
R 11
R 25
T
L 8
B
B
R 40
T
B

8
25
40
1

4
B
T
B
T

-1
-1
0

3
L 9
T
R 2

2

출처: Devin.KR 자체 제작