medianheap

Problem Description

Remember the priority_queue data structure that pops out the greatest element every time? Now, you have to implement a data structure that is similar to priority_queue, but does not pop out the greatest element, but pops out the element according to the following rules:

1. If the size of the queue is odd, pop out the middle element. (i.e. the median)
2. Otherwise, pop out the element to the left of the middle.

Input

The first line of input will contain N, the number of instructions.
The following N lines of input will contain either a PUSH x, where you will be required to push an integer x into the queue, or a POP instruction, where you will be required to pop an integer out of the queue according to the instructions above.

Output

Your output should contain a list of space-seperated integers, which represents the resultant queue in ascending order.
Your output should be terminated with a newline.

Limits

Subtask 1 (36%): 1 ≤ N ≤ 1 000
Subtask 2 (64%): 1 ≤ N ≤ 1 000 000
Subtask 3 (0%): As per sample testcases

Sample Input 1

5
PUSH 5
PUSH 2
POP
PUSH 3
PUSH 9

Sample Output 1

3 5 9