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.
from collections import defaultdict
n=input()
minn=1000001
maxx=0
a=defaultdict(int)
ans=[]
count=0
for i in range(0,n):
    x=map(int,raw_input().split())
    if x[0]==1:
        if x[1]>maxx:
            maxx=x[1]
        if x[1]<minn:
            minn=x[1]
        a[x[1]]+=1
        count+=1
    elif x[0]==2:
        if a[x[1]]>0:
            a[x[1]]-=1
            if a[x[1]]==0 and x[1]==maxx:
                k=a.keys()
                maxx=0
                #print k
                for j in range(0,len(k)):
                    if a[k[j]]>0 and k[j]>maxx:
                        maxx=k[j]
                        #print maxx
            if a[x[1]]==0 and x[1]==minn:
                k=a.keys()
                minn=1000001
                for j in range(0,len(k)):
                    if a[k[j]]>0 and k[j]<minn:
                        minn=k[j]        
            count-=1
        else:
            ans.append(-1)
    elif x[0]==3:
        if count>0:
            ans.append(maxx)
        else:
            ans.append(-1)
    elif x[0]==4:
        if count>0:
            ans.append(minn)
        else:
            ans.append(-1)
#print a
#print maxx
#print minn
for i in range(0,len(ans)):
    print ans[i]