#include <bits/stdc++.h>
using namespace std;


vector<int> fancyNumbers(int N, vector<int> Q[])
{
    priority_queue<int> right;
    priority_queue<int,vector<int>,greater<int>> left;

    vector<int> res;

    for(int i=0;i<N;i++){
        int t = Q[i][0];
        if(t==1){
            int x = Q[i][1];

            int temp = left.size() + right.size();

            if(temp%3==2){
                if(x>=right.top()){
                    left.push(x);
                }
                else{
                    right.push(x);
                    left.push(right.top());
                    right.pop();
                }
            }
            else{
                if(left.size()==0){
                    right.push(x);
                }
                else{
                    if(x<=left.top()){
                        right.push(x);
                    }
                    else{
                        left.push(x);
                        right.push(left.top());
                        left.pop();
                    }
                }
            }
        }
        else{
            if(left.size()==0){
                res.push_back(-1);
            }
            else{
                res.push_back(left.top());
            }
        }
    }
    return res;
}

int main(){
    int N;
    cin>>N;

    vector<int> Q[N];
    for(int i=0;i<N;i++){
        int q;
        cin>>q;
        Q[i].push_back(q);
        if(q==1){
            int x;
            cin>>x;
            Q[i].push_back(x);
        }
    }

    vector<int> res = fancyNumbers(N,Q);
    for(auto i : res){
        cout<<i<<endl;
    }
}