#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,t;
priority_queue<int,vector<int>,greater<int> > qa;
priority_queue<int> qb;
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t;
		if(qa.size()==0 || t>=qa.top()) qa.push(t);
		else qb.push(t);
		if(i%2){
			if(qa.size()-qb.size()>1){
				qb.push(qa.top());
				qa.pop(); 
			}
			if(qb.size()>qa.size()){
				qa.push(qb.top());
				qb.pop(); 
			}
			cout<<qa.top()<<endl;
		} 
		
	}
	return 0;
}