RT

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main() {
    cin >> t;
    while(t--) {
        priority_queue<int,vector<int>,less<int>>q1;//大根堆
        priority_queue<int,vector<int>,greater<int>>q2;//小根堆     
        while(scanf("%d",&n)){
            if (n==0) break;
            if (n==-1) {
                if ((q1.size()+q2.size())%2==0) {
                    cout << q1.top() << endl;
                    q1.pop();
                }
                else {
                    cout << q2.top() << endl;
                    q2.pop();
                }
            }
            else {
                if (q2.size()==0||n>q2.top()) q2.push(n);
                else q1.push(n);
            }
            while(q1.size()>q2.size()) q2.push(q1.top()),q1.pop();
            while(q2.size()>q1.size()+1) q1.push(q2.top()),q2.pop();
        }
    }
    return 0;
}