배달 대기판 뒤집기

문제

한 배달 앱은 아직 배달원에게 배정하지 않은 주문을 대기판에 한 줄로 표시한다. 대기판에는 맨 앞과 맨 뒤가 있으며, 처음에는 주문이 하나도 없다. 운영 중에는 일반 주문 접수, 긴급 주문 접수, 배정, 취소, 대기판 뒤집기의 다섯 종류 사건이 발생한다. 앱에 기록된 사건을 주어진 순서대로 처리하려 한다. 주문은 접수될 때마다 고유한 주문 번호를 받는다. 일반 주문과 긴급 주문을 구분하지 않고, 처음 접수된 주문의 번호는 1이며 이후 접수되는 주문의 번호는 바로 전에 접수된 주문의 번호보다 1 크다. 이미 배정되거나 취소된 주문의 번호를 다시 사용하지 않는다. 접수 이외의 사건은 새 주문 번호를 만들지 않는다. 사건 1은 일반 주문 접수다. 새 주문 하나를 현재 대기판의 맨 뒤에 추가한다. 사건 2는 긴급 주문 접수다. 새 주문 하나를 현재 대기판의 맨 앞에 추가한다. 여러 긴급 주문이 연속으로 접수되면 나중에 접수된 주문이 더 앞에 놓인다. 사건 3은 배정이다. 현재 대기판의 맨 앞 주문 하나를 제거하고 그 주문 번호를 기록한다. 사건 4는 취소다. 현재 대기판의 맨 뒤 주문 하나를 제거하고 그 주문 번호를 기록한다. 사건 3이나 사건 4가 발생했을 때 대기판이 비어 있다면 아무것도 제거하지 않고 0을 기록한다. 사건 5는 대기판 뒤집기다. 현재 대기 중인 모든 주문의 표시 순서를 반대로 바꾼다. 뒤집기가 끝난 뒤 발생하는 사건은 바뀐 순서의 맨 앞과 맨 뒤를 기준으로 처리한다. 대기판에 주문이 없거나 하나만 있으면 표시 순서는 그대로다. 뒤집기는 주문 번호를 바꾸지 않는다. 모든 사건을 처리하면서 배정 또는 취소 때 기록한 값을 순서대로 출력하고, 마지막으로 대기판에 남아 있는 주문 수를 출력하는 프로그램을 작성하라.

입력

첫째 줄에 사건 수 N이 주어진다. N은 1 이상 100,000 이하의 정수다.
다음 N개 줄에는 사건을 나타내는 정수 하나가 각각 주어진다. 각 정수는 1 이상 5 이하다. 각 사건의 의미는 지문에 설명한 것과 같다. 입력에 추가 매개변수는 없다.

출력

사건 3 또는 사건 4가 발생할 때마다 기록한 주문 번호를 한 줄에 하나씩 발생 순서대로 출력한다. 해당 사건을 처리할 때 대기판이 비어 있었다면 0을 출력한다. 모든 사건을 처리한 뒤에는 대기판에 남은 주문 수를 마지막 줄에 출력한다. 사건 3과 사건 4가 한 번도 발생하지 않았더라도 마지막 줄은 반드시 출력한다.

10
1
1
2
5
3
2
4
5
3
4

2
3
1
4
0

7
3
5
4
2
1
5
3

0
0
2
1

4
1
2
5
1

3

출처: Devin.KR 자체 제작