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
def heapify(pos,heap):
    left=(pos*2)+1
    right=left+1
    l=len(heap)
    #print l
    if left<l and heap[left]>heap[pos]:
        big=left
    else:
        big=pos
    if right<l and heap[right]>heap[big]:
        big=right
    if pos!=big:
        heap[pos],heap[big]=heap[big],heap[pos]
        heapify(big,heap)
def push(val,heap):
    heap.append(val)
    pos=len(heap)-1
    i=pos
    par=(pos-1)/2
    while par>=0 and heap[par]<heap[i]:
        heap[par],heap[i]=heap[i],heap[par]
        i=par
        par=(par-1)/2
def pop(heap):
    heap[0]=heap[len(heap)-1]
    del heap[len(heap)-1]
    if len(heap)>1:
        #print "Heap"
        heapify(0,heap)
n=input()
minheap=[]
maxheap=[]
count=[0]*1000000
for i in xrange(n):
    a=map(int,raw_input().split())
    if a[0]==1:
        if count[a[1]]==0:
            push(a[1],maxheap)
            heapq.heappush(minheap,a[1])
        count[a[1]]+=1
        
    elif a[0]==2:
        if count[a[1]]==0:
            print -1
        else:
            count[a[1]]-=1
    elif a[0]==3:
        while len(maxheap)>0 and count[maxheap[0]]==0:
            pop(maxheap)
        if len(maxheap)>0:    
            print maxheap[0]
        else:
            print -1
    elif a[0]==4:
        while len(minheap)>0 and count[minheap[0]]==0:
            heapq.heappop(minheap)
        if len(minheap)>0:
            print minheap[0]
        else:
            print -1