堆应该是没写错，毕竟用了好几遍了

#include<bits/stdc++.h>
using namespace std;
int num;
short zf;
char ch;
int read()
{
	num=0;
	ch=getchar();
	zf=1;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')zf=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num*zf;
}
bool cmp(int x,int y)
{
	return x>=y;
}
struct priority_que{
	int a[2000001];
	int t=0;
	int size(){return t;}
	int top(){return a[1];}
	void pop()
	{
		if(t==0)return;
		int x=1;
		a[1]=a[t];
		t--;
		while(x*2<=t)
		{
			if(cmp(a[x],a[2*x])&&(x*2+1>t?1:cmp(a[x],a[x*2+1])))break;
			if(x*2+1>t)
			{
				swap(a[x],a[2*x]);
				x=2*x;
				continue;
			}
			else if(cmp(a[2*x],a[2*x+1]))
			{
				swap(a[x],a[2*x]);
				x=2*x;
			}
			else
			{
				if(cmp(a[x],a[2*x+1]))break;
				swap(a[x],a[2*x+1]);
				x=2*x+1;
			}
		}
	}
	void push(int s)
	{
		a[++t]=s;
		int x=t;
		while(x>1&&!cmp(a[x/2],a[x]))
		{
			swap(a[x],a[x/2]);
			x/=2;
		}
	}
	bool empty(){return t==0;}
	void clear(){t=0;}
	void out()
	{
		for(int i=1;i<=t;i++)
		{
			printf("%d ",a[i]);
		}
		putchar('\n');
	}
}q;
bool cmp2(int x,int y)
{
	return x<=y;
}
struct priority_que2{
	int a[2000001];
	int t=0;
	int size(){return t;}
	int top(){return a[1];}
	void pop()
	{
		if(t==0)return;
		int x=1;
		a[1]=a[t];
		t--;
		while(x*2<=t)
		{
			if(cmp2(a[x],a[2*x])&&(x*2+1>t?1:cmp2(a[x],a[x*2+1])))break;
			if(x*2+1>t)
			{
				swap(a[x],a[2*x]);
				x=2*x;
				continue;
			}
			else if(cmp2(a[2*x],a[2*x+1]))
			{
				swap(a[x],a[2*x]);
				x=2*x;
			}
			else
			{
				if(cmp2(a[x],a[2*x+1]))break;
				swap(a[x],a[2*x+1]);
				x=2*x+1;
			}
		}
	}
	void push(int s)
	{
		a[++t]=s;
		int x=t;
		while(x>1&&!cmp2(a[x/2],a[x]))
		{
			swap(a[x],a[x/2]);
			x/=2;
		}
	}
	bool empty(){return t==0;}
	void clear(){t=0;}
}q2;
int n,mid;
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int T=read();
	while(T--)
	{
		q.clear();
		q2.clear();
		mid=-1;
		while((n=read())!=0)
		{
			if(n==-1)
			{
				cout<<mid<<endl;
				if(q2.empty())
				{
					mid=-1;
					continue;
				}
				mid=q2.top();
				q2.pop();
				while(q.size()>q2.size())
				{
					q2.push(mid);
					mid=q.top();
					q.pop();
				}
				continue;
			}
			if(mid==-1)
			{
				mid=n;
				continue;
			}
			if(n<=mid)
			{
				q.push(n);
			}
			else
			{
				q2.push(n);
			}
			while(q.size()>q2.size())
			{
				q2.push(mid);
				mid=q.top();
				q.pop();
			}
			while(q2.size()>q.size()+1)
			{
				q.push(mid);
				mid=q2.top();
				q2.pop();
			}
		}
	}
	return 0;
}