ans

#include<bits/stdc++.h>
using namespace std;
int n,x;
priority_queue<int> q2;
priority_queue<int,vector<int>,greater<int>> q1;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		q1.push(x);
		if(i%2==1){
			int t1=(i+1)/2;
			int t2=i/2;
			while(q1.size()>t1){
				int x=q1.top();
				q1.pop();
				q2.push(x);
			}
			while(!q1.empty()&&!q2.empty()&&q1.top()<q2.top()){
				int x=q1.top();
				q1.pop();
				int y=q2.top();
				q2.pop();
				q1.push(y);
				q2.push(x);
			}
			cout<<q1.top()<<endl;
		}
	}
	return 0;
}