#include<bits/stdc++.h>
using namespace std;
priority_queue<int , vector<int> , less <int > > _q;
priority_queue<int , vector<int> , greater <int> > __q;
int n,rubbish;
int main(){
	cin>>n>>rubbish;
	_q.push(rubbish);
	cout<<_q.top()<<endl;
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		if(x>_q.top())__q.push(x);
		else _q.push(x);
		while(abs( int(_q.size()) - int(__q.size()) ) >1){
			if(_q.size()>__q.size()){
				__q.push(_q.top());
				_q.pop();
			}
			else{
				_q.push(__q.top());
				__q.pop();
			}
			if(i%2==1){
				if(_q.size()>__q.size())cout<<_q.top();
				else cout<<__q.top();
			}
		}
	}
	return 0;
}