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 sys
import heapq
import traceback  
def insert(x):
	if count[x]==0:
		heapq.heappush(maxq,-x)
		heapq.heappush(minq,x)
		count[x]+=1
	else:
		count[x]+=1		
 
def remove(x):
 
	if count[x]==0:
		return False
	else:
		count[x]-=1
		return True		
 
def minim():

	if len(minq)==0:
		return -1

	while count[minq[0]]==0 and len(minq)>0:
		heapq.heappop(minq)
	if len(minq)==0:
		return -1	
	return minq[0]			
	
 
def maxim():
 	if len(maxq)==0:
 		print 0
		return -1
	while len(maxq)>0 and count[abs(maxq[0])]==0:
			heapq.heappop(maxq)
	if len(maxq)==0:
		return -1	
	return -maxq[0]	
 
maxq = []
minq = []
n  = int(raw_input())
count = [0]*100005
for i in xrange(n):
	arr = [int(x) for x in str(sys.stdin.readline()).split()]
	if arr[0]==1:
		insert(arr[1])
	elif arr[0]==2:
		res = remove(arr[1])
		if not res:
			print -1
	elif arr[0]==3:
		print maxim()
	else:	
		print minim()