You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

In this assignment, you will implement a Priority Queue that supports three fundamental operations: pushing a key, peeking at the highest priority key, and popping the highest priority key.

A Priority Queue is an abstract data structure that maintains a collection of elements, each with an associated priority (key). For this problem, you will implement a Priority Queue, and treats larger keys as having higher priority.

A common and efficient way to implement this is by using a Max Heap. A Max Heap is a binary tree that satisfies two special properties:

• Shape Property: It is a complete binary tree. This means all levels of the tree are fully filled, except possibly the last level, which is filled from left to right.
• Max-Heap Property: The key of any node is greater than or equal to the keys of its children. This property ensures that the element with the maximum key is always at the root of the tree.

You will process a sequence of commands, each representing one of the following operations:

1. push k: Insert an integer key k into the priority queue.
2. peek: Get the maximum key from the priority queue without removing it. If the priority queue is empty, return null.
3. pop: Extract the maximum key from the priority queue. This operation should remove and return the key. If the priority queue is empty, return null.

---

Format

Input

• The first line contains a single integer $N$ ($1 \leq N \leq 10^5$), representing the number of operations to perform.
• The next $N$ lines each contain an operation. The operation will be one of the following:
  • push k: The string push followed by a single space and an integer key $k$ ($-10^9 \leq k \leq 10^9$).
  • peek: The literal string peek.
  • pop: The literal string pop.

Output

• For each peek or pop operation, print the integer value of the key on a new line. If the priority queue is empty when the operation is called, print null.
• The push operation should not produce any output.

---

Samples

7
push 10
push 5
push 15
peek
pop
peek
pop

15
15
10
10

Explanation: We can visualize the heap as an array.

1. push 10: Heap state: [10]
2. push 5: Heap state: [10, 5]
3. push 15: Heap state: [10, 5, 15]. The sift-up operation is performed on 15. Heap becomes: [15, 5, 10].
4. peek: The root 15 is the maximum. It is printed. The heap is unchanged. State: [15, 5, 10].
5. pop: The root 15 is the maximum. It is printed and removed. The last element 10 moves to the root. Heap state: [10, 5]. The sift-down operation runs on 10, but no swaps are needed.
6. peek: The root 10 is the maximum. It is printed. Heap state: [10, 5].
7. pop: The root 10 is the maximum. It is printed and removed. The last element 5 moves to the root. Heap state: [5].

---

13
push 50
push 30
push 70
peek
pop
push 20
push 40
peek
pop
pop
pop
pop
pop

70
70
50
50
40
30
20
null

Explanation:

1. After push 50, push 30, push 70, the heap state is [70, 30, 50].
2. peek: Prints 70. Heap is unchanged.
3. pop: Prints 70. Heap becomes [50, 30].
4. push 20: Heap becomes [50, 30, 20].
5. push 40: Heap becomes [50, 30, 20, 40]. sift-up(40) swaps it with 30. Heap state: [50, 40, 20, 30].
6. peek: Prints 50. Heap is unchanged.
7. pop: Prints 50. Heap becomes [40, 30, 20].
8. pop: Prints 40. Heap becomes [30, 20].
9. pop: Prints 30. Heap becomes [20].
10. pop: Prints 20. Heap becomes [] (empty).
11. pop: The heap is empty. The output is null.

---

Hint

• A solution with $O(N^2)$ overall complexity (e.g., using an unsorted or sorted array) will be too slow.
• With a Max Heap implementation, insertion (push) and extraction (pop) operations should ideally take about $O(\log M)$ time, where $M$ is the current number of elements in the heap. The peek operation should take $O(1)$ time.
• The test cases are structured as follows:
  • Test Cases 1-5: Small-scale inputs to check the basic heap logic (sift-up, sift-down).
  • Test Cases 6-15: Large-scale inputs with a mix of push, pop, and peek operations to test efficiency and correctness, including calls on an empty heap.

---

Limitation

1s, 128MiB for each test case.