#include <bits/stdc++.h>
  using namespace std;
const int N=1e5+5;
int m,t,a[N],b[N],x,y,i;
void aa(int t)
{
	int u,v;
	a[++x]=t;
//	cout<<"x"<<x<<endl;
	u=x;
	while (u>1)
	{
		v=u>>1;
		if (a[v]<a[u]) swap(a[u],a[v]);
		else return;
		u=v;
	}
}
void ba(int t)
{
	int u,v;
	b[++y]=t;
	// cout<<"y"<<y<<endl;
	u=y;
	while (u>1)
	{
		v=u>>1;
		if (b[v]>b[u]) swap(b[u],b[v]);
		else return;
		u=v;
	}
}
void ad()
{
	int u,v;
	swap(a[1],a[x--]);
//	cout<<"xx"<<a[1]<<" "<<a[x+1]<<endl;
	u=1;
	while (u<=(x>>1))
	{
		v=u<<1;
		if (v+1<=x && a[v]<a[v+1]) v++;
		if (a[u]<a[v]) swap(a[u],a[v]);
		else return;
		u=v;
	}
}
void bd()
{
	int u,v;
	swap(b[1],b[y--]);
//	cout<<"yy"<<y<<endl;
	u=1;
	while (u<=(y>>1))
	{
		v=u<<1;
		if (v+1<=y && b[v]>b[v+1]) v++;
		if (b[u]>b[v]) swap(b[u],b[v]);
		else return;
		u=v;
	}
}
int main()
{
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin>>m;
	while (m--)
	{
		x=0;
		y=0;
		while (true)
		{
			cin>>t;
			if (!t) break;
			if (t==-1)
			{
				if ((x+y)&1)
				{
					cout<<b[1]<<endl;
					bd();
					// cout<<"b:";
					// for (i=1;i<=y;i++)
					// {
					// 	cout<<b[i]<<" ";
					// }
					// cout<<endl;
				}
				else
				{
					cout<<a[1]<<endl;
					ad();
					// cout<<"a:";
					// for (i=1;i<=x;i++)
					// {
					// 	cout<<a[i]<<" ";
					// }
					// cout<<endl;
				}
			}
			else
			{
				if ((!x && !y) || t>b[1])
				{
					ba(t);
					if (y>((x+y)>>1))
					{
						aa(b[1]);
						bd();
					}
				}
				else
				{
					aa(t);
					if (x>((x+y)>>1))
					{
						ba(a[1]);
						ad();
					}
				}
				// cout<<x<<"a:";
				// for (i=1;i<=x;i++)
				// {
				// 	cout<<a[i]<<" ";
				// }
				// cout<<endl;
				// cout<<y<<"b:";
				// for (i=1;i<=y;i++)
				// {
				// 	cout<<b[i]<<" ";
				// }
				// cout<<endl;
			}
		}
	}
	return 0;
}