In this problem you must create a Heap data structure to store the integers, where the following operations are defined:

• Insert(x) - add into Heap x;
• Exctract - extract from the Heap the maximum element (and delete it).

Input

The first line contains the number of commands n (1 ≤ n ≤ 105), then a sequence of n operations, each in a separate line.

Each command has the following format: "0 number" or "1", which means respectively the operations Insert (number) and Extract. The inserted numbers range from 1 to 107 inclusive.

It is guaranteed that when the Extract command is executed, there is at least one element in the structure.

Output

For each extraction command, print the number obtained by executing the Extract command.