6593: ALDS1_9_C : Priority Queue
[Creator : ]
Description
A priority queue is a data structure which maintains a set $S$ of elements, each of with an associated value (key), and supports the following operations:
- insert(S,k): insert an element $k$ into the set $S$
- extractMax(S): remove and return the element of $S$ with the largest key
Input
Multiple operations to the priority queue $S$ are given.
Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.
The input ends with "end" operation.
Each operation is given by "insert $k$", "extract" or "end" in a line. Here, $k$ represents an integer element to be inserted to the priority queue.
The input ends with "end" operation.
Output
For each "extract" operation, print the element extracted from the priority queue $S$ in a line.
Constraints
The number of operations $≤2,000,000$
$0≤k≤2,000,000,000$
$0≤k≤2,000,000,000$
Sample 1 Input
insert 8
insert 2
extract
insert 10
extract
insert 11
extract
extract
end
Sample 1 Output
8
10
11
2