#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <utility>
#include <map>
#include <stack>
#include <set>
#include <vector>
#include <queue>
#include <deque>
#include <sstream>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define LL long long
#define Pair pair<int,int>
#define LOWBIT(x) x & (-x)
using namespace std;

const int MOD=1e9+7;
const int INF=0x7ffffff;
const int magic=348;

priority_queue<Pair> q;
int n;
int a[200048];
vector<int> ans;

struct node
{
	int left,right;
	int minn,min_pos;
}tree1[600048],tree2[600048];

void build1(int cur,int left,int right)
{
	tree1[cur].left=left;tree1[cur].right=right;
	if (left==right)
	{
		if (left%2==1) tree1[cur].minn=a[left]; else tree1[cur].minn=INF;
		tree1[cur].min_pos=left;
	}
	else
	{
		int mid=(left+right)>>1;
		build1(cur*2,left,mid);
		build1(cur*2+1,mid+1,right);
		if (tree1[cur*2].minn<tree1[cur*2+1].minn)
		{
			tree1[cur].minn=tree1[cur*2].minn;
			tree1[cur].min_pos=tree1[cur*2].min_pos;
		}
		else
		{
			tree1[cur].minn=tree1[cur*2+1].minn;
			tree1[cur].min_pos=tree1[cur*2+1].min_pos;
		}
	}
}

set<Pair> s;

void build2(int cur,int left,int right)
{
	tree2[cur].left=left;tree2[cur].right=right;
	if (left==right)
	{
		if (left%2==0) tree2[cur].minn=a[left]; else tree2[cur].minn=INF;
		tree2[cur].min_pos=left;
	}
	else
	{
		int mid=(left+right)>>1;
		build2(cur*2,left,mid);
		build2(cur*2+1,mid+1,right);
		if (tree2[cur*2].minn<tree2[cur*2+1].minn)
		{
			tree2[cur].minn=tree2[cur*2].minn;
			tree2[cur].min_pos=tree2[cur*2].min_pos;
		}
		else
		{
			tree2[cur].minn=tree2[cur*2+1].minn;
			tree2[cur].min_pos=tree2[cur*2+1].min_pos;
		}
	}
}

Pair query1(int cur,int left,int right)
{
	//cout<<cur<<' '<<tree1[cur].left<<' '<<tree1[cur].right<<endl;
	if (left<=tree1[cur].left && tree1[cur].right<=right)
		return mp(tree1[cur].minn,tree1[cur].min_pos);
	int mid=(tree1[cur].left+tree1[cur].right)>>1;
	Pair res1=mp(INF,INF),res2=mp(INF,INF);
	if (left<=mid) res1=query1(cur*2,left,right);
	if (mid+1<=right) res2=query1(cur*2+1,left,right);
	if (res1.x<res2.x) return res1; else return res2;
}

Pair query2(int cur,int left,int right)
{
		//cout<<tree2[cur].left<<' '<<tree2[cur].right<<endl;
	if (left<=tree2[cur].left && tree2[cur].right<=right)
		return mp(tree2[cur].minn,tree2[cur].min_pos);
	int mid=(tree2[cur].left+tree2[cur].right)>>1;
	Pair res1=mp(INF,INF),res2=mp(INF,INF);
	if (left<=mid) res1=query2(cur*2,left,right);
	if (mid+1<=right) res2=query2(cur*2+1,left,right);
	if (res1.x<res2.x) return res1; else return res2;
}

int main ()
{
	//freopen ("1.txt","r",stdin);
	//freopen ("2.txt","w",stdout);
	int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++) scanf("%d",&a[i]);
	build1(1,1,n);build2(1,1,n);
	Pair ins,res,ress,r=query1(1,1,n);
	r.x=-r.x;
	q.push(r);
	s.insert(mp(1,0));s.insert(mp(n,1));
	int left,right;
	set<Pair>::iterator iter;
	while (!q.empty())
	{
		//for (iter=s.begin();iter!=s.end();iter++)
		//	cout<<iter->x<<' '<<iter->y<<endl;
		//cout<<"*******"<<endl;
		res=q.top();res.x=-res.x;q.pop();
		//cout<<res.x<<' '<<res.y<<endl;
		ans.pb(res.x);
		iter=s.lower_bound(mp(res.y,-INF));
		if (iter->y==0) ++iter;
		right=(*iter).x;
		left=(*--iter).x;//cout<<"*";
		//left=find_anc_l(res.y);right=find_anc_r(res.y);
		//cout<<left<<' '<<right<<endl;
		//cout<<res.y+1<<' '<<right<<"#"<<endl;
		if (res.y%2==1) ress=query2(1,res.y+1,right); else ress=query1(1,res.y+1,right);
		ans.pb(ress.x);
		//cout<<res.x<<' '<<res.y<<' '<<ress.x<<' '<<ress.y<<' '<<left<<' '<<right<<endl;
		/*if (res.y+1<ress.y)
		{
			//cout<<"*";
			prel[res.y+1]=res.y+1;
			prer[ress.y-1]=ress.y-1;
		}
		cout<<find_anc_r(2)<<endl;
		cout<<prer[2]<<' '<<prer[3]<<endl;
		if (res.y!=left) prer[res.y-1]=res.y-1;
		if (ress.y!=right) prel[ress.y+1]=ress.y+1;*/
		if (res.y+1<ress.y)
		{
			if (res.y%2==1)
			{
				ins=query2(1,res.y+1,ress.y-1);
				//cout<<res.y+1<<' '<<ress.y-1<<' '<<ins.x<<endl;
				ins.x=-ins.x;
				q.push(ins);
			}
			else
			{
				ins=query1(1,res.y+1,ress.y-1);
				//cout<<res.y+1<<' '<<ress.y-1<<' '<<ins.x<<endl;
				ins.x=-ins.x;
				q.push(ins);
			}
		}
		if (res.y!=left)
		{
			if (res.y%2==1)
			{
				ins=query1(1,left,res.y-1);
				ins.x=-ins.x;
				//cout<<left<<' '<<res.y-1<<' '<<ins.x<<endl;
				q.push(ins);
			}
			else
			{
				ins=query2(1,left,res.y-1);
				//cout<<left<<' '<<res.y-1<<' '<<ins.x<<endl;
				ins.x=-ins.x;
				q.push(ins);
			}
		}
		if (ress.y!=right)
		{
			if (ress.y%2==1)
			{
				ins=query2(1,ress.y+1,right);
				//cout<<ress.y+1<<' '<<right<<' '<<ins.x<<endl;
				ins.x=-ins.x;
				q.push(ins);
			}
			else
			{
				ins=query1(1,ress.y+1,right);
				//cout<<ress.y+1<<' '<<right<<' '<<ins.x<<endl;
				ins.x=-ins.x;
				q.push(ins);
			}
		}
		if (res.y+1!=ress.y)
		{
			s.insert(mp(res.y+1,0));
			s.insert(mp(ress.y-1,1));
		}
		if (res.y!=left)
		{
			s.insert(mp(res.y-1,1));
		}
		else
			s.erase(mp(res.y,0));
		if (ress.y!=right)
		{
			s.insert(mp(ress.y+1,0));
		}
		else
			s.erase(mp(ress.y,1));
	}
	for (i=0;i<ans.size();i++) printf("%d ",ans[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 25580