PriorityQueue Comparator

In the previous problem, priority queue elements are retrieved in the natural order (ascending order). However, we can customize this ordering.

For this, we need to create our own comparator class that implements the Comparator interface.

To read more about this please find the resources here.

Task:

You need to think of a data structure and implement it such that it can help you in answering the below-mentioned queries.

You are given Q queries, in each query you are given two integers x and y:

if x = 1 then insert the integer y to your data structure.
if x = 2 then print an integer denoting the maximum element currently present in your data-structure, if there are no elements present then print -1
if x = 3 then remove the maximum element currently present in your data structure, if there is no element present then don’t do anything.

1 <= Q <= 10⁵

1 <= x <= 3

1 <= y <= 1000

First line of input contains a single integer Q.

Next, Q lines each contain two integers x and y for that query.

For each query in which x = 2 print its answer in separate lines.

Input 1: 

 6
 2 -1
 1 5
 1 2
 2 -1
 3 -1
 2 -1

Output 1:

 -1
 5
 2

Explanation 1:

 Query 1: x = 2 but as we don't have any element so we will print -1.
 Query 2: x = 1 we will insert 5 to our data structure.
 Query 3: x = 1 we will insert 2 to our data structure.
 Query 4: x = 2 the maximum element is 2=5
 Query 5: x = 3 we will remove the maximum element i.e 5
 Query 6: x = 2 the maximum element now is 2