Minimum Heap

Interview

Time limit1sMemory limit128 MB

Summary
Implement a min-heap to support inserting natural numbers and repeatedly extracting the smallest, printing 0 when empty.
Level

Easy3 of 10

Topics
Heap, Implementation
Solved
No attempts yet

Problem

Write a program that manages a collection of natural numbers with a min-heap. The collection starts empty and must support the following operations.

  1. If a natural number x is given, insert x into the collection.
  2. If 0 is given, print the smallest value in the collection and remove that value. If the collection is empty, print 0.

Input

The first line contains the number of operations N (1 <= N <= 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 collection. If x is 0, print and remove the smallest value in the collection. Each x is either 0 or a natural number less than 2^31; negative integers are not given.

Output

For each operation where 0 is given, print one line containing the result. If the collection is empty when a print-and-remove operation is requested, print 0.

Examples1

  1. Example 1

    Input
    9
0
12345678
1
2
0
0
0
0
32
    Expected output
    0
1
2
12345678
0