//{{{By oToToT
// C
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#endif

// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>

#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif

#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
using namespace std;
/* include everything for Kotori~ <3 */

typedef long long lld;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef pair<int,int> PII;
typedef pair<lld,lld> PLL;
typedef pair<int,lld> PIL;
typedef pair<lld,int> PLI;
template<typename T>
using maxHeap = priority_queue<T,vector<T>,less<T>>;
template<typename T>
using minHeap = priority_queue<T,vector<T>,greater<T>>;
/* define some types for Ruby! */

#define F1(i,s,n) for(int i=s;i<int(n);i++)
#define F(i,s,n,k) for(int i=s;i!=int(n);i+=(k))
#define WC(a) while(a--)
/* make loop easier for Di~a~ */

#define FF first
#define SS second
#define SZ(x) ((int)((x).size()))
#define PB push_back
#define ALL(x) (x).begin(), (x).end()
/* define some weird thing for Ainyan~n~ */

#ifdef __linux__
#define gc getchar_unlocked
#elif _WIN32
#define gc getchar
#elif __APPLE__
#define gc getchar
#endif
template<typename T, class = typename is_integral<T>::type>
inline void GET(T &_){T __=1;char c=gc();_=0;while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')__=-1,c=gc();while(c>='0'&&c<='9')_=_*10+c-'0',c=gc();_*=__;}
inline void GET(llf &_){llf __=1,___=0;char c=gc();_=0;while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')__=-1,c=gc();while(c>='0'&&c<='9')_=_*10+c-'0',c=gc();if(c=='.'){c=gc();for(llf w=10;c>='0'&&c<='9';w*=10)___=___+(c-'0')/w,c=gc();}_+=___;_*=__;}
inline void GET(lf &_){lf __=1,___=0;char c=gc();_=0;while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')__=-1,c=gc();while(c>='0'&&c<='9')_=_*10+c-'0',c=gc();if(c=='.'){c=gc();for(lf w=10;c>='0'&&c<='9';w*=10) ___=___+(c-'0')/w,c=gc();}_+=___;_*=__;}
inline void GET(float &_){float __=1,___=0;char c=gc();_=0;while((c<'0'||c>'9')&&c!='-')c=gc();if(c=='-')__=-1,c=gc();while(c>='0'&&c<='9')_=_*10+c-'0',c=gc();if(c=='.'){c=gc();for(float w=10;c>='0'&&c<='9';w*=10) ___=___+(c-'0')/w,c=gc();}_+=___;_*=__;}
inline void GET(char *_){char c=gc();while(c==' '||c=='\n'||c=='\t')c=gc();size_t __=0;for(_[__++]=c;c!=' '&&c!='\n'&&c!='\t'&&c!='\0';_[__++]=c)c=gc();_[__]='\0';}
inline void GET(string &_){char c=gc();while(c==' '||c=='\n'||c=='\t')c=gc();for(_.PB(c);c!=' '&&c!='\n'&&c!='\t'&&c!='\0';_.PB(c))c=gc();}
template <typename T, typename ...Args>
inline void GET(T &x, Args& ...args){GET(x);GET(args...);}
#undef gc
/* make reading quicker for Ma~ri~ <3 */

#ifdef __linux__
#define pc putchar_unlocked
#elif _WIN32
#define pc putchar
#elif __APPLE__
#define pc putchar
#endif
inline void SHOW(const int &a){printf("%d",a);};
inline void SHOW(const unsigned int &a){printf("%u",a);};
inline void SHOW(const llu &a){printf("%llu",a);};
inline void SHOW(const lld &a){printf("%lld",a);};
inline void SHOW(const lf &a){printf("%lf",a);};
inline void SHOW(const long &a){printf("%ld",a);};
inline void SHOW(const char a[]){for(size_t _=0;a[_]!='\0';_++)pc(a[_]);};
inline void SHOW(const char &a){pc(a);};
inline void SHOW(const bool &a){pc(a?'1':'0');};
template<typename A, typename B>
inline void SHOW(const pair<A,B>& a){pc('(');SHOW(a.FF);pc(',');pc(' ');SHOW(a.SS);pc(')');}
template<typename T,size_t N>
inline void SHOW(const array<T,N>& a){pc('[');for(auto _=a.cbegin();_!=a.cend();_++){if(_!=a.begin())pc(' ');SHOW(*_);}pc(']');}
template<typename T>
inline void SHOW(const vector<T> &a){pc('[');for(auto _=a.cbegin();_!=a.cend();_++){if(_!=a.begin())pc(' ');SHOW(*_);}pc(']');}
template <typename T, typename ...Args>
inline void SHOW(const T& x,const Args& ...args){SHOW(x);SHOW(args...);}
#undef pc
/* make showing things easier and quicker for Uchida Aya */

bool debug=0;
inline void DEBUG(const int &a){if(debug)fprintf(stderr,"%d",a);};
inline void DEBUG(const unsigned int &a){if(debug)fprintf(stderr,"%u",a);};
inline void DEBUG(const llu &a){if(debug)fprintf(stderr,"%llu",a);};
inline void DEBUG(const lld &a){if(debug)fprintf(stderr,"%lld",a);};
inline void DEBUG(const llf &a){if(debug)fprintf(stderr,"%Lf",a);};
inline void DEBUG(const lf &a){if(debug)fprintf(stderr,"%lf",a);};
inline void DEBUG(const long &a){if(debug)fprintf(stderr,"%ld",a);};
inline void DEBUG(const char a[]){if(debug)fprintf(stderr,"%s",a);};
inline void DEBUG(const char &a){if(debug)fprintf(stderr,"%c",a);};
inline void DEBUG(const bool &a){if(debug)fprintf(stderr,(a?"1":"0"));};
template<typename A,typename B>
inline void DEBUG(const pair<A,B>& a){DEBUG('(');DEBUG(a.FF);DEBUG(", ");DEBUG(a.SS);DEBUG(")");}
template<typename T,size_t N>
inline void DEBUG(const array<T,N> &a){DEBUG('[');for(auto _=a.cbegin();_!=a.cend();_++){if(_!=a.begin())DEBUG(' ');SHOW(*_);}DEBUG(']');}
template<typename T>
inline void DEBUG(const vector<T> &a){DEBUG('[');for(auto _=a.cbegin();_!=a.cend();_++){if(_!=a.begin())DEBUG(' ');SHOW(*_);}DEBUG(']');}
template <typename T, typename ...Args>
inline void DEBUG(const T& x,const Args& ...args){DEBUG(x);DEBUG(args...);}
/* Let's debug with Nico~Nico~Ni~ */
//}}}
const int N = 200000 + 5;
const int INF = 1<<30;
class SegTree{
	private:
		int size;
		PII nodes[4*N];
		inline int lc(int x){return 2*x+1;}
		inline int rc(int x){return 2*x+2;}
		void build(int l, int r ,int id, PII arr[]){
			if(r-l==1){
				nodes[id]=arr[l];
				return;
			}
			int mid=(l+r)>>1;
			build(l, mid, lc(id), arr);
			build(mid, r, rc(id), arr);
			nodes[id] = min(nodes[lc(id)], nodes[rc(id)]);
		}
		PII query(int ql, int qr, int l, int r, int id){
			if(qr <= l or r <= ql) return {INF,INF};
			if(ql <= l and r <= qr) return nodes[id];
			int mid=(l+r)>>1;
			return min(query(ql, qr, l, mid, lc(id)), query(ql, qr, mid, r, rc(id)));
		}
		void modify(int ql, int qr, int l, int r, int id, PII v){
			if(qr <= l or r <= ql) return;
			if(ql <= l and r <= qr){
				nodes[id]=v;
				return;
			}
			int mid=(l+r)>>1;
			modify(ql, qr, l, mid, lc(id), v);
			modify(ql, qr, mid, r, rc(id), v);
			nodes[id] = min(nodes[lc(id)], nodes[rc(id)]);
		}
	public:
		void build(int n, PII arr[]){
			size=n;
			build(0, size, 0, arr);
		}
		PII query(int l, int r){
			// DEBUG("> querying [",l,", ",r,")\n");
			// PII rr = query(l, r, 0, size, 0);
			// DEBUG("> ",rr,'\n');
			// return rr;
			return query(l, r, 0, size, 0);
		}
		void modify(int p, PII v){
			modify(p, p+1, 0, size, 0, v);
		}
} odd, even;

int arr[N], ans[N];
PII o[N], e[N];

int main(int argc, char* argv[]){
	if(argc>1&&string(argv[1])=="-D") debug=1;
	int n; GET(n);
	fill(o, o+n, (PII){INF,INF});
	fill(e, e+n, (PII){INF,INF});
	F1(i, 0, n){
		GET(arr[i]);
		if(i&1) o[i]={arr[i],i};
		else e[i]={arr[i],i};
	}
	odd.build(n, o);
	even.build(n, e);
	set<int> block;
	block.insert(0);
	block.insert(n);
	minHeap<PII> pq;
	pq.push(even.query(0, n));
	for(int i=0;i<(n/2);i++){
		PII pos = pq.top();pq.pop();
		if(pos.SS & 1){
			PII sec = even.query(pos.SS, *block.upper_bound(pos.SS));
			odd.modify(pos.SS, {INF,INF});
			even.modify(sec.SS, {INF,INF});
			auto it = block.upper_bound(pos.SS);
			it--;
			pq.push(odd.query(*it, pos.SS));
			pq.push(even.query(pos.SS, sec.SS));
			pq.push(odd.query(sec.SS, *block.upper_bound(sec.SS)));
			block.insert(pos.SS);
			block.insert(sec.SS);
			ans[i*2]=pos.FF;
			ans[i*2+1]=sec.FF;
		}else{
			PII sec = odd.query(pos.SS, *block.upper_bound(pos.SS));
			even.modify(pos.SS, {INF,INF});
			odd.modify(sec.SS, {INF,INF});
			auto it = block.upper_bound(pos.SS);
			it--;
			pq.push(even.query(*it, pos.SS));
			pq.push(odd.query(pos.SS, sec.SS));
			pq.push(even.query(sec.SS, *block.upper_bound(sec.SS)));
			block.insert(pos.SS);
			block.insert(sec.SS);
			ans[i*2]=pos.FF;
			ans[i*2+1]=sec.FF;
		}
	}
	F1(i, 0, n) SHOW(ans[i], " \n"[i==n-1]);
	return 0;
}

Measured memory_bytes: 29680