#include <cstdio>
#include <queue>
#include <string>
#include <iostream>
using namespace std;
priority_queue<int,vector<int>,less<int> > small;
priority_queue<int,vector<int>,greater<int> > big;
int main()
{
	int n;
	scanf("%d",&n);
	int x;
	string s;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		small.push(x);
	}
	int cnt=n&1;
	scanf("%d",&n);
	while(n--)
	{
		cin>>s;
		if(s=="add")
		{
			cnt^=1;
			scanf("%d",&x);
			small.push(x);
			while(cnt&1?small.size()>big.size()+1:small.size()>big.size())
			{
				big.push(small.top());
				small.pop();
			}
			while(small.top()>big.top())
			{
				small.push(big.top()),big.push(small.top());
				small.pop();big.pop();
			}
		}
		else printf("%d\n",small.top());
	}
	return 0;
}