rt

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