#include <bits/stdc++.h>
using namespace std;
set <int> lf,rt;
void adjust() {
    if (lf.size()> rt.size()+1)
    {
        rt.insert(*lf.rbegin());
        lf.erase(*lf.rbegin());
    }
    else if (lf.size()< rt.size())
    {
        lf.insert(*rt.begin());
        rt.erase(*rt.begin());
    }
}
void add (int x)
{
    if (x>*rt.begin())
        rt.insert(x);
    else
        lf.insert(x);
}
int main()
{
    int t,a;
    scanf("%d",&t);
    while (t--)
    {
        lf.clear();
        rt.clear();
        while (1)
        {
            scanf("%d",&a);
            if (a==0)break;
            else if (a!=-1)
                {
                    add (a);
                    adjust();
                }
            else if (a==-1)
                {
                    printf("%d\n",*lf.rbegin());
                    lf.erase(*lf.rbegin());
                    adjust();
                }
        }
    }
    return 0;
}