31785번 - 시소 배열

문제

비어 있는 배열 $A$가 있다. 당신은 다음 두 종류의 질의를 총 $Q$개 처리해야 한다.

• 1 $x$: 배열의 가장 뒤에 정수 $x$를 삽입한다.
• 2: 현재 배열의 길이를 $N$이라 하자. 배열을 앞 $\left\lfloor{N\over 2}\right\rfloor$개의 원소와 뒤 $\left\lceil{N\over 2}\right\rceil$개의 원소 두 부분으로 나눈 후, 원소들의 합이 더 작은 부분을 배열에서 삭제한다. 만약 두 부분의 합이 같을 경우, 앞 $\left\lfloor{N\over 2}\right\rfloor$개의 원소를 삭제한다. 이후 삭제된 부분의 원소의 합을 출력한다. 이 형식의 질의는 배열의 길이가 2ドル$ 이상일 때만 주어진다.

모든 질의를 올바르게 처리하고, 그 후 배열 $A$에 저장된 모든 원소를 차례대로 출력하는 프로그램을 작성하여라.

입력

첫 번째 줄에 질의의 수 $Q$가 주어진다. $(3\le Q\le 500\ 000)$

두 번째 줄부터 $Q$개의 줄에 걸쳐 질의가 아래와 같은 형식 중 하나로 주어진다.

• 1 $x$: $(1\le x\le 1,000円),ドル $x$는 정수
• 2

2번 질의가 1번 이상 주어지며, 모든 2번 질의는 배열의 길이가 2ドル$ 이상일 때 주어짐이 보장된다.

출력

각 2번 질의에 대한 답을 차례대로 각 줄에 걸쳐 출력한다. 이후 다음 줄에 모든 질의를 처리한 후 배열 $A$에 저장된 모든 원소를 차례대로 출력한다.

제한

노트

어떤 실수 $x$에 대해, $\lfloor{x}\rfloor$는 $n \le x$을 만족하는 가장 큰 정수 $n$의 값으로 정의된다. 마찬가지로, $\lceil{x}\rceil$은 $n \ge x$을 만족하는 가장 작은 정수 $n$의 값으로 정의된다.