#include<bits/stdc++.h>
using namespace std;

int n,mid,a[2000005];
priority_queue<int>pq_n;
priority_queue<int,vector<int>,greater<int>>pq_x;

int main(){
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	
	cout << (mid = a[1]) << '\n';
	for(int i = 2; i <= n; i += 2){
		a[i] < mid ? pq_n.push(a[i]) : pq_x.push(a[i]);
		a[i+1] < mid ? pq_n.push(a[i+1]) : pq_x.push(a[i+1]);
		
		if(pq_x.size() > pq_n.size()){
			pq_n.push(mid);
			mid = pq_x.top();
			pq_x.pop();
		}
		else if(pq_n.size() > pq_x.size()){
			pq_x.push(mid);
			mid = pq_n.top();
			pq_n.pop();
		}
		
		cout << mid << '\n';
	}
	
	return 0;
}