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.
q = input()
arr = [0]*(100001)
noe = 0
mini = 10**9
maxi = -1
for _ in xrange(q):
    xi = raw_input().split()
    x = int(xi[0])
    y = int(xi[-1])
    if(x==1):
        arr[y]+=1
        noe+=1
        mini = min(y,mini)
        maxi = max(y,maxi)
    elif(x==2):
        if(arr[y]==0):
            print -1
        else:
            arr[y]-=1
            while(mini <100001 and arr[mini]==0 ):
            	mini+=1
            while( maxi > 0 and arr[maxi]==0):
            	maxi-=1
            noe-=1
    elif(x==3):
        if(noe==0):
            print -1
        else:
            print maxi
    else:
        if(noe==0):
            print -1
        else:
            print mini