#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	scanf("%d",&t);
	while(t-- > 0) {
		int cnt = 0;
		int x;
		priority_queue<int> qmax;
		priority_queue<int, vector<int> ,greater<int> > qmin;
		do {
			scanf("%d",&x);
			if(x != -1) {
				cnt++;
				if(cnt & 1) {
					if(!qmax.empty() && x < qmax.top()) {
						qmin.push(qmax.top());
						qmax.pop();
						qmax.push(x);
					} else {
						qmin.push(x);
					}
				} else {
					if(!qmin.empty() && x > qmin.top()) {
						qmax.push(qmin.top());
						qmin.pop();
						qmin.push(x);
					} else {
						qmax.push(x);
					}
				}
			} else {
				if(cnt & 1) {
					printf("%d\n",qmin.top());
					qmin.pop();
				} else {
					printf("%d\n",qmax.top());
					qmax.pop();
				}
				cnt--;
			}
		} while(x != 0);
	}
	return 0;
}