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 heapq
MX = 10 ** 5 + 1
Q = int(raw_input())
a, b = [], []
c = [0] * MX
n = 0
for loop in xrange(Q):
	q = map(int, raw_input().split())
	if   q[0] == 1:
		heapq.heappush(a, -q[1])
		heapq.heappush(b, q[1])
		c[q[1]] += 1
		n += 1
	elif q[0] == 2:
		if c[q[1]] == 0:
			print -1
		else:
			c[q[1]] -= 1
			n -= 1
	elif q[0] == 3:
		if n == 0:
			print -1
		else:
			while c[-a[0]] == 0:
				heapq.heappop(a)
			print -a[0]
	elif q[0] == 4:
		if n == 0:
			print -1
		else:
			while c[b[0]] == 0:
				heapq.heappop(b)
			print b[0]