#include<bits/stdc++.h>
using namespace std;
int main(){
	int n;
	cin>>n;
	int q[n];
	for(int i=0;i<n;i++){
		cin>>q[i];
	}
	int mid=q[0];
	cout<<mid<<endl;
	priority_queue< int/*, vector<int>, greater<int>*/ > right; //小根堆 
	priority_queue< int > left;                             //大根堆 
	for(int i=1;i<n;i+=2){
		int a=q[i];
		int b=q[i+1];
		if(a<mid&&b>mid){
			left.push(a);
			right.push(-b);
		} else if(a>mid&&b<mid){
			left.push(b);
			right.push(-a);
		} else if(a<mid&&b<mid){
			left.push(a);
			left.push(b);
			right.push(-mid);
			mid=left.top();
			left.pop();
		} else {
			right.push(-a);
			right.push(-b);
			left.push(mid);
			mid=-right.top();
			right.pop();
		}
		cout<<mid<<endl;
	}
}