/*
*/

#pragma GCC optimize("O3")
#define _CRT_SECURE_NO_WARNINGS
#include <fstream>
#include <iostream>
#include <string>
#include <complex>
#include <math.h>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <stdio.h>
#include <stack>
#include <algorithm>
#include <list>
#include <ctime>

#include <memory.h>
#include <assert.h>

#define y0 sdkfaslhagaklsldk

#define y1 aasdfasdfasdf
#define yn askfhwqriuperikldjk
#define j1 assdgsdgasghsf
#define tm sdfjahlfasfh
#define lr asgasgash
#define norm asdfasdgasdgsd
#define have adsgagshdshfhds
#define ends asdgahhfdsfshdshfd

#define eps 1e-11
#define M_PI 3.141592653589793
#define bsize 512

#define ldouble long double
using namespace std;

#define bs 1000000007
const int N = 1300031;

int n;
int ar[N];
set<int> blockers;
set<int>::iterator it;
vector<int> ans;

pair<int,int> t[N][2];

int flag[N];

void push(int v)
{
	if (flag[v])
		{
			swap(t[v*2][0],t[v*2][1]);
			swap(t[v*2+1][0],t[v*2+1][1]);
			flag[v*2]^=1;
			flag[v*2+1]^=1;
			flag[v]=0;
		}
}

pair<int,int> better(pair<int,int> p1,pair<int,int> p2){
	if (p1.first!=p2.first)
	{
		if (p1.first<p2.first)
			return p1;
		return p2;
	}
	return p1;
}

pair<int,int> get(int v,int tl,int tr,int l,int r,int rem){
	if (l>r)
		return make_pair(1e9,-1);
	if (tl==l&&tr==r)
		return t[v][rem];
	push(v);
	int tm=tl+tr;
	tm/=2;
	return better(get(v*2,tl,tm,l,min(r,tm),rem),get(v*2+1,tm+1,tr,max(tm+1,l),r,rem));
}

void run_kill(int v,int tl,int tr,int ps)
{
	if (tl==tr)
	{
		t[v][0]=t[v][1]=make_pair(1000000000,-1);
		return;
	}
	push(v);
	int tm=tl+tr;
	tm/=2;
	if (ps<=tm)
		run_kill(v*2,tl,tm,ps);
	else
		run_kill(v*2+1,tm+1,tr,ps);
	for (int i=0;i<2;i++)
	{
		t[v][i]=better(t[v*2][i],t[v*2+1][i]);
	}
}

void update(int v,int tl,int tr,int l,int r)
{
	if (l>r)
		return;
	if (tl==l&&tr==r)
	{
		swap(t[v][0],t[v][1]);
		flag[v]^=1;
		return;
	}
	push(v);
	int tm=tl+tr;
	tm/=2;
	update(v*2,tl,tm,l,min(r,tm));
	update(v*2+1,tm+1,tr,max(tm+1,l),r);
	for (int i=0;i<2;i++)
	{
		t[v][i]=better(t[v*2][i],t[v*2+1][i]);
	}
}

void kill(int ps)
{
	blockers.insert(ps);
	//cout<<"@@@"<<ps<<endl;

	update(1,1,n,ps+1,n);
	run_kill(1,1,n,ps);
}

void build(int v,int tl,int tr)
{
	if (tl==tr)
	{
		t[v][tl%2]=make_pair(ar[tl],tl);
		t[v][1-tl%2]=make_pair(1e9,-1);
		return;
	}
	int tm=tl+tr;
	tm/=2;
	build(v*2,tl,tm);
	build(v*2+1,tm+1,tr);
	for (int i=0;i<2;i++)
	{
		t[v][i]=better(t[v*2][i],t[v*2+1][i]);
	}
}

int main(){
	//freopen("tree.in","r",stdin);
	//freopen("tree.out","w",stdout);
	//freopen("input.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0);
	//cin.tie(0);

	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>ar[i];
	}

	build(1,1,n);

	blockers.insert(n+1);

	//cout<<"@"<<endl;

	for (int i=1;i<=n/2;i++)
	{
		pair<int,int> p=get(1,1,n,1,n,1);
	//	cout<<p.first<<"%"<<p.second<<endl;
		int ans_val=p.first;
		int ans_pos=p.second;
		ans.push_back(ans_val);
		it=blockers.lower_bound(ans_pos);
		int next_cut=(*it);
//		cout<<"@"<<next_cut<<"@"<<endl;
		//cout<<ans_pos+1<<"%!"<<next_cut-1<<endl;
		pair<int,int> p2=get(1,1,n,ans_pos+1,next_cut-1,0);
	//	cout<<p2.first<<" "<<p2.second<<endl;
		kill(ans_pos);
		kill(p2.second);
		ans.push_back(p2.first);
	}

	for (int i=0;i<ans.size();i++)
	{
		if (i)
			cout<<" ";
		cout<<ans[i];
	}
	cout<<endl;

	cin.get(); cin.get();
	return 0;
}


Measured memory_bytes: 28148