#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n;
priority_queue<int> q1;
priority_queue<int,vector<int>,greater<int> > q2;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		if(i==1) q2.push(x);
		if(x>q2.top()) q2.push(x);
		else q1.push(x);
		if(i%2!=0){
			if(q2.size()-1==q1.size()) cout<<q2.top()<<"\n";
			else{
				while(q2.size()-1>q1.size()){
					q1.push(q2.top());
					q2.pop();
				}
				cout<<q2.top()<<"\n";
			}
 		}
 	}
}