#include<bits/stdc++.h>
#define ll long long
using namespace std;
class fhq{
    private:
        struct node{
            int size,data,vis;
            node *l,*r;
        }*root=0,zero;
    public:
        node *newnode(int x){
            node *ip=new node;
            ip->data=x,ip->vis=rand(),ip->size=1,ip->l=ip->r=NULL;
            return ip;
        }
        void pushup(node *ip){
            if(ip==NULL) return;
            ip->size=1;
            if(ip->l) ip->size+=ip->l->size;
            if(ip->r) ip->size+=ip->r->size;
        }
        void split(node *ip,int val,node *&l,node *&r){
            if(ip==NULL) l=r=NULL;
            else{
                if(ip->data<=val){
                    l=ip;
                    split(ip->r,val,ip->r,r);
                }
                else{
                    r=ip;
                    split(ip->l,val,l,ip->l);
                }
                pushup(ip);
            }
        }
        node* merge(node *&l,node *&r){
            if(l==NULL) return r;
            if(r==NULL) return l;
            if(l->vis<=r->vis){
                l->r=merge(l->r,r);
                pushup(l);
                return l;
            }
            r->l=merge(l,r->l);
            pushup(r);
            return r;
        }
        void add(int x){
            node *a=NULL,*b=NULL;
            split(root,x,a,b);
            node *tmp1=newnode(x),*tmp2=merge(a,tmp1);
            root=merge(tmp2,b);
        }
        void del(int x){
            node *a=NULL,*b=NULL,*c=NULL;
            split(root,x,b,c);
            split(b,x-1,a,b);
            node *tmp1=merge(b->l,b->r),*tmp2=merge(a,tmp1);
            root=merge(tmp2,c);
            if(b) delete b;
        }
        int kth(int x){
            node *a=NULL,*b=NULL;
            split(root,x-1,a,b);
            int ans=1;
            if(a) ans+=a->size;
            root=merge(a,b);
            return ans;
        }
        int val(int th){
            node *ip=root;
            while(ip!=NULL){
                int ls=0,rs=0;
                if(ip->l!=NULL) ls=ip->l->size;
                if(ip->r!=NULL) rs=ip->r->size;
                if(ls+1==th) break;
                else if(ls>=th) ip=ip->l;
                else th-=ls+1,ip=ip->r;
            }
            return ip->data;
        }
        int pre(int x){
            node *a=NULL,*b=NULL,*ans=NULL;
            split(root,x-1,a,b);
            for(ans=a;ans->r;ans=ans->r);
            root=merge(a,b);
            return ans->data;
        }
        int nxt(int x){
            node *a=NULL,*b=NULL,*ans=NULL;
            split(root,x,a,b);
            for(ans=b;ans->l;ans=ans->l);
            root=merge(a,b);
            return ans->data;
        }
        void midfor(node *ip=0){
            if(!ip) ip=root;
            if(ip->l) midfor(ip->l);
//          cout<<ip->data<<" ";
            if(ip->r) midfor(ip->r);
        }
}t;
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int f;
	cin>>f;
	while(f--){
		int n,len;
		cin>>n;
		while(1){
			int x;
			cin>>x;
			if(x>0){
				t.add(x);
				len++;
			}
			if(x==0){
				break;
			}
			if(x==-1){
				if(len%2==1){
					cout<<t.val((len+1)/2)<<endl;
					t.del(t.val((len+1)/2));
				}
				else{
					cout<<t.val(len/2)<<endl;
					t.del(t.val(len/2));
				}
			}
		}
	}
}