#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int n,m,a[maxn];
priority_queue<int>q1;
priority_queue<int,vector<int>,greater<int>>q2;
int main()
{
    #ifdef LOCAL
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
    #endif
    
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    for(int i=1;i<=(n>>1);++i)
        q1.push(a[i]);
    for(int i=(n>>1)+1;i<=n;++i)
        q2.push(a[i]);
    scanf("%d",&m);
    char opt[10];
    int w;
    while (m--)
    {
        scanf("%s",opt+1);
        if(opt[1]=='a')
        {
            scanf("%d",&w);
            if(w>q1.top())
            {
                if(q2.size()>q1.size())
                {
                    q1.push(q2.top());
                    q2.pop();q2.push(w);
                }
                else
                {
                    q2.push(w);
                }
            }
            else
            {
                if(q1.size()>q2.size())
                {
                    q2.push(q1.top());
                    q1.pop();q1.push(w);
                }
                else
                {
                    q1.push(w);
                }
            }
        }
        else
        {
            if(q1.size()==q2.size()||q1.size()>q2.size())
            {
                printf("%d\n",q1.top());
            }
            else if(q1.size()<q2.size())
            {
                printf("%d\n",q2.top());
            }
        }
    }
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/