Max Heap

Interview

Time limit1sMemory limit256 MB

Summary

Process N insert and pop-max operations on an initially empty max heap, printing the maximum or 0 when empty.

Level: Easy3 of 10
Topics: Heap
Solved: No attempts yet

Problem

The max heap is a widely used data structure. Write a program that supports the following two operations with a max heap.

Insert a natural number $x$ into the array.
Print the largest value in the array and remove that value from the array.

The program starts with an empty array.

Input

The first line contains the number of operations $N$ ( $1 \le N \le 100\,000$ ). Each of the next $N$ lines contains one integer $x$ describing an operation. If $x$ is a natural number, insert $x$ into the array. If $x$ is 0, print the largest value in the array and remove that value from the array. Every natural number in the input is smaller than $2^{31}$ .

Output

Print one answer per line, as many times as 0 appears in the input. If the array is empty when the largest value is requested, print 0.

Examples3

Example 1

Input

Expected output

Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
10
4
1
5
3
2
0
0
0
0
0
```
Expected output
```
5
4
3
2
1
```