#include<cstdio>
#include<map> 
#include<algorithm>
#include<string.h>
#define N 100005

using namespace std;

int num[N], snum[N], n, loc[N], tag[N]; // loc存储，num对应位置的元素在排序后的新下标值！tag标记对应的排序后的下标值是否被使用过 


int check(int f){
	// 寻找左侧第一个f值对应的没有使用过的下标值
	int l = 1, r = n, mid, ans;
	while(l<=r){
		mid = (l+r)>>1;
		if( snum[mid] == f && tag[mid] == 0){
			ans = mid; // 记录答案 
			r = mid-1; // 去左区间寻找 
		}
		else if(snum[mid] == f && tag[mid] == 1){
			l = mid+1; // 去右区间寻找 
		}else if( snum[mid] > f)	
			r = mid-1; // 去左区间寻找 
		else
			l = mid+1;
	} 
	
	tag[ans]=1; // 标记
	
	return  ans;
} 

int main(void)
{
	int i, j;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", num+i);
		snum[i] = num[i];
	}	 
	
	sort(snum+1, snum+n+1); // 升序排序
	 
	for(i=1;i<=n;i++)	loc[i] = check( num[i] ); // 得到从原下标到新有序下标的映射 

	
	// 求中位数
	memset(tag, 0, sizeof(tag)); // 清空
	tag[ loc[1] ] = 1; // 第一个元素
	printf("%d\n", num[1]);
	
	int now = loc[1]; // 当前中位数( 映射后的下标值 ) 
	int a, b, tmp;
	
	for(i=1;i<(n+1)/2;i++, puts("")){  // 剩余一共 n/2 次，这里不对，n不一定是奇数！ 
		a = loc[i*2];
		b = loc[i*2+1]; // a和b是新加入的两个数的映射下标值
		
		if(a > b)	swap(a,b); // a为小的数，b为大的数 
		 
		if( a < now && b > now  ){ // 1. 
			printf("%d", snum[now]); // 中位数不变 
		}else if ( b < now ){
			// 2. 两个数都比now小，寻找now左侧第一个数(二分)，这里不能二分好像！不对！！！！没有办法二分啊！ 
			
			tmp = now;
			for(j=now-1;j>0;j--){
				if( tag[j] ){
					tmp = j;
					break; 
				}
			}
			
			if( b < tmp && tmp != now){  // 都比j小，则中位数就是j 
				printf("%d", snum[tmp]);
				now = tmp; // 中位数 
			}else{
				// 其它情况，则中位数是较大的那个数b
				printf("%d", snum[b]);
				now = b;
			}
		} else {
			// 2. 两个数都比now大，寻找now右侧第一个数(二分)，这里不能二分好像！不对！！！！没有办法二分啊！ 
			tmp = now;
			for(j=now+1;j<=n;j++){
				if( tag[j] ){
					tmp = j;
					break;
				}
			}
			
			if( a > tmp && tmp != now){  // 都比r大，则中位数就是r 
				printf("%d", snum[tmp]);
				now = tmp; // 中位数 
			}else{
				// 其它情况，则中位数是较小的那个数a 
				printf("%d", snum[a]);
				now = a;
			}
		} 
		
		tag[a]=1;
		tag[b]=1; // 标记新加入的两个数 
	} 
	return 0;
}