#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
const long long inf=1e18;
using namespace std;
int n,a;
priority_queue<int,vector<int> >q1;
priority_queue<int,vector<int>,greater<int> >q2;
int main(){
	cin>>n;
	cin>>a;
	q1.push(a);
	cout<<q1.top()<<endl;
	for(int i=2;i<=n;i++){
		cin>>a;
		if(a>q1.top())q2.push(a);
		else q1.push(a);
		while(abs(int(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==1){
			cout<<(q1.size()>q2.size())?q1.top():q2.top();
			cout<<endl;
		}
	}
}