Monk was asked to answer some queries in an interview. He is given an empty array A. Queries are of 4 types:-
1. 1 X - Add number X to the array A.
2. 2 X - Remove a single instance of number X from the array A. If not possible, print "-1" without the quotes.
3. 3 - Find the maximum element in the array A.
4. 4 - Find the minimum element in the array A.  

Input:
The first line contains the integer Q.
The next Q lines will each contain a query like the ones mentioned above.

Output: 
For queries 3 and 4, print the answer in a new line. If the array is empty for query 3 and 4, then print "-1" without the quotes.

Constraints:
1 ≤ Q ≤ 100000
1 ≤ X ≤ 100000

SAMPLE INPUT
5
1 5
1 9
1 6
3
2 1

SAMPLE OUTPUT
9
-1

Explanation

There are 5 queries.
Query 1 - 5 is added to the array.
Query 2 - 9 is added to the array.
Query 3 - 6 is added to the array.
Query 4 - The maximum element in the array is 9.
Query 5 - Since there is no element in the array with value 1, so the output is -1.
import collections
import heapq

def solve(xss):
    res = []
    counts = collections.defaultdict(lambda: 0)
    min_q = []
    max_q = []
    for xs in xss:
        if xs[0] == 1:
            counts[xs[1]] += 1
            heapq.heappush(min_q, xs[1])
            heapq.heappush(max_q, -xs[1])
        elif xs[0] == 2:
            if not counts[xs[1]]: res.append(-1)
            else: counts[xs[1]] -= 1
        elif xs[0] == 3:
            while len(max_q) and not counts[-max_q[0]]: heapq.heappop(max_q)
            x = -1
            if len(max_q): x = -max_q[0]
            res.append(x)
        elif xs[0] == 4:
            while len(min_q) and not counts[min_q[0]]: heapq.heappop(min_q)
            x = -1
            if len(min_q): x = min_q[0]
            res.append(x)
    return '\n'.join(str(r) for r in res)

if __name__ == '__main__':
    xss = [map(int, raw_input().split()) for _ in range(int(raw_input()))]
    print solve(xss)