#include<bits/stdc++.h>
using namespace std;
priority_queue <int> sm;
priority_queue <int, vector<int>, greater<int> > big;
int k, p, mid = -INT_MAX;
void change(){
	if(sm.size() < big.size())
		while(sm.size() < big.size()){
			sm.push(big.top());
			big.pop();
		}	
	if(sm.size() > big.size() + 1)
		while(sm.size() > big.size()){
			big.push(sm.top());
			sm.pop();
		}
}
int main(){
	scanf("%d", &k);
	while(k--){
		while(sm.empty()) sm.pop();
		while(big.empty()) big.pop();
		while(scanf("%d", &p)){
			if(p == 0) break;
			if(p != -1){
				if(p >= mid) sm.push(p);
				else big.push(p);
				change(); 
				mid = sm.top();
			}
			else{
				if(big.size() == sm.size()){
					int mid2 = big.top();
					printf("%d\n", min(mid, mid2));
					if(mid < mid2) sm.pop();
					else big.pop();
					change();
					mid = sm.top();
				}
			}
		}
	}
	return 0;
}