// Slower C++ solution:
#include <stdio.h>

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <cctype>

#include <string>

#include <cstring>

#include <algorithm>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <ctime>

#include <vector>

#include <fstream>

#include <list>

#include <iomanip>

#include <numeric>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

#define ms(s) memset(s, 0, sizeof(s))

const int INF = 1e9;

inline int read(){

	int X = 0,w = 0 ;

	char ch = 0;

	while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}

	while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();

	return w ? -X : X;

}

int n;

int m=1;

int a[800005];

int seg[2][800005];

int ans[200005];

struct node

{

	int a,b;

	int mint;

};

void update(int k)

{

	int odd;

	int pos=k;

	odd=k%2;

	k+=m-1;

	seg[odd][k]=pos;

	seg[(odd+1)%2][k]=INF;

	while(k>1)

	{

		k/=2;

		for(int i=0;i<2;i++)

		{

			if(seg[i][k*2]==INF and seg[i][k*2+1]!=INF)

			{

				seg[i][k]=seg[i][k*2+1];

			}

			else if(seg[i][k*2+1]==INF&&seg[i][k*2]!=INF)

			{

				seg[i][k]=seg[i][k*2];

			}

			else if(seg[i][k*2]!=INF&&seg[i][k*2+1]!=INF)

			{

				if(a[seg[i][k*2]]<a[seg[i][k*2+1]])

				{

					seg[i][k]=seg[i][k*2];

				}

				else

				{

					seg[i][k]=seg[i][k*2+1];

				}

			}

		}

	}

}

int query(int l,int r,int k,int l1,int r1)

{

	int odd=l%2;

	if(l<=l1 and r>=r1)

	{

		return seg[odd][k];

	}

	if(r<l1 or l>r1)

	{

		return INF;

	}

	else

	{

		int x=query(l,r,k*2,l1,(l1+r1)/2);

		int y=query(l,r,k*2+1,(l1+r1+1)/2,r1);

		if(x==INF and y!=INF)

		{

			return y;

		}

		else if(x!=INF and y==INF)

		{

			return x;

		}

		else if(x==INF and y==INF)

		{

			return INF;

		}

		else

		{

			if(a[x]<a[y])

			{

				return x;

			}

			else

			{

				return y;

			}

		}

	}

}

bool operator >(node x,node y)

{

	if(x.mint!=INF and y.mint!=INF)

	{

		return a[x.mint]>a[y.mint];

	}

	else if(x.mint==INF and y.mint!=INF)

	{

		return true;

	}

	else if(x.mint!=INF and y.mint==INF)

	{

		return false;

	}

	return true;

}

int main()

{

	cin>>n;

	for(int i=0;i<800000;i++)

	{

		a[i]=INF;

		seg[0][i]=INF;

		seg[1][i]=INF;

	}

	while(m<n)

	{

		m*=2;

	}

	for(int i=1;i<=n;i++)

	{

		cin>>a[i];

	}

	for(int i=1;i<=m;i++)

	{

		update(i);

	}

	priority_queue<node,vector<node>,greater<node> > pq;

	node init={1,n,query(1,n,1,1,m)};

	pq.push(init);

	int id=1;

	while(id<=n and !pq.empty())

	{

		node f=pq.top();

		pq.pop();

		ans[id++]=f.mint;

		int tmp=query(f.mint+1,f.b,1,1,m);

		node nx,dx={f.mint+1,f.b,tmp};

		if(f.a<f.mint-1)

		{

			tmp=query(f.a,f.mint-1,1,1,m);

			nx={f.a,f.mint-1,tmp};

			pq.push(nx);

		}

		ans[id++]=dx.mint;

		node sec,thir;

		if(dx.a<dx.mint-1)

		{

			tmp=query(dx.a,dx.mint-1,1,1,m);

			sec={dx.a,dx.mint-1,tmp};

			pq.push(sec);

		}

		if(dx.mint+1<dx.b)

		{

			tmp=query(dx.mint+1,dx.b,1,1,m);

			thir={dx.mint+1,dx.b,tmp};

			pq.push(thir);

		}

	}

	for(int i=1;i<=n;i++)

	{

		cout<<a[ans[i]]<<" ";

	}

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 1.6953189835257798x):
#include<cstdio>

#include<iostream>

#include<algorithm>

#include<string>

#include<math.h>

#include<vector>

#include<queue>

#include<map>

#include<stack>

#include<fstream>

#include<stdlib.h>

#include<set>

#include<climits>

#include<cmath>  

#include<memory.h> 

#include<sstream>

#include<time.h>

#include<iomanip>

using namespace std;

const unsigned long long BIGEST=1000000000000000000+1000000000000000000;

const long long BIGER=1000000000000000000;

const int BIG=1000000000;

const int MOD=1000000007;

const long long LMOD=1000000007;

#define F first

#define S second

#define p2 pair<int,int>

#define cb make_pair

int n;

int ar[200005];

vector<int>v[200005];

p2 p[200005];

struct seg

{

	int mnid[800005][2];

	int ch(int x,int l=1,int r=n,int k=1)

	{

		if(r<x||x<l)return 0;

		//cout<<"!"<<x<<" "<<l<<" "<<r<<" "<<k<<" ";

		if(ar[x]<ar[mnid[k][x%2]])mnid[k][x%2]=x;

		//cout<<mnid[k][0]<<" "<<mnid[k][1]<<endl;

		if(l!=r)

		{

			ch(x,l,(l+r)/2,k*2);

			ch(x,(l+r)/2+1,r,k*2+1);

		}

		//cout<<"!"<<x<<" "<<l<<" "<<r<<" "<<k<<" ";

		//cout<<mnid[k][0]<<" "<<mnid[k][1]<<endl;

		return 0;

	}

	int q(int a,int b,int v,int l=1,int r=n,int k=1)

	{

		//cout<<" "<<a<<" "<<b<<" "<<v<<" "<<l<<" "<<r<<" "<<k<<endl;

		if(r<a||b<l)return 0;

		//cout<<">"<<a<<" "<<b<<" "<<v<<" "<<l<<" "<<r<<" "<<k<<endl;

		if(a<=l&&r<=b)return mnid[k][v];

		if(l!=r)

		{

			int t1,t2;

			t1=q(a,b,v,l,(l+r)/2,k*2);

			t2=q(a,b,v,(l+r)/2+1,r,k*2+1);

			if(ar[t1]<ar[t2])return t1;

			else return t2;

		}

		return 0;

	}

}T;

int g=0;

int fu(int l,int r)

{

	//cout<<l<<" "<<r<<endl;

	int id=++g;

	p2 t;

	t.F=T.q(l,r,l%2);

	t.S=T.q(t.F,r,(l+1)%2);

	//cout<<"("<<t.F<<","<<t.S<<")";

	if(t.F>l)v[id].push_back(fu(l,t.F-1));

	if(t.S>t.F+1)v[id].push_back(fu(t.F+1,t.S-1));

	if(r>t.S)v[id].push_back(fu(t.S+1,r));

	p[id].F=ar[t.F];

	p[id].S=ar[t.S];

	return id;

}

int main()

{

	ar[0]=BIG;

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&ar[i]);

		T.ch(i);

	}

	fu(1,n);

	set<pair<p2,int > >q;

	q.insert(cb(p[1],1));

	pair<p2,int> t;

	while(!q.empty())

	{

		t=*q.begin();

		q.erase(t);

		printf("%d %d ",t.F.F,t.F.S);

		//cout<<t.S<<" ";

		for(int i=0;i<v[t.S].size();i++)q.insert(cb(p[v[t.S][i]],v[t.S][i]));

	}

	return 0;

}