#pragma comment(linker, "/STACK:60777216")  

#include <cassert>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<complex>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<string>
#include<cstdlib>
#include<memory.h>
#include<ctime>
#include<bitset>
#include<fstream>
#include<queue>
#include<stack>
#include<unordered_map>
#include<unordered_set>

using namespace std;

typedef long double ld;

typedef long long ll;
typedef pair<int,int>	pii;
typedef pair<ld,ld>	pdd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef pair<ll,ll> pl;

#define FOR(i,a,b)		for(int i=(a);i<(b);i++)
#define REP(i,n)		FOR(i,0,n)
#define SORT(v)			sort((v).begin(),(v).end())
#define UN(v)			SORT(v),(v).erase(unique((v).begin(),(v).end()),(v).end())
#define CL(a,b)			memset(a,b,sizeof a)
#define pb				push_back

int n;
int p[222222];
int inv[222222];
set<int> breaks;

struct Node{
	Node() {
		l=r=0;
		lf=rg=0;
	}
	int l,r;
	int val;
	Node* lf;
	Node* rg;
};

Node* root1;
Node* root2;
const int inf = 1e9+7;

Node* buildTree(int l,int r){
	Node* x = new Node();
	x->l=l;
	x->r=r;
	x->val=inf;
	if(l!=r){
		x->lf = buildTree(l,(l+r)/2);
		x->rg = buildTree((l+r)/2+1,r);
	}
	return x;
}
void setVal(Node* curr,int pos,int val){
	if(curr->l>pos) return;
	if(curr->r<pos) return;
	if(curr->l==pos && curr->r==pos){
		curr->val = val;
	}else{
		setVal(curr->lf,pos,val);
		setVal(curr->rg,pos,val);
		curr->val = min(curr->lf->val,curr->rg->val);
	}
}

int getMin(Node* curr,int l,int r){
	if(curr->l>r) return inf;
	if(curr->r<l) return inf;
	if(l<=curr->l && curr->r<=r) return curr->val;
	return min(getMin(curr->lf,l,r),getMin(curr->rg,l,r));
}

void swapTrees(Node* t1, Node* t2, int l, int r){
	if(t1->l==t1->r)return;
	if(t1->l > r) return;
	if(t1->r < l) return;

	if(l<=t1->lf->l && t1->lf->r<=r){
		swap(t1->lf,t2->lf);
	}else swapTrees(t1->lf,t2->lf,l,r);
	
	if(l<=t1->rg->l && t1->rg->r<=r){
		swap(t1->rg,t2->rg);
	}else swapTrees(t1->rg,t2->rg,l,r);
	
	t1->val = min(t1->lf->val,t1->rg->val);
	t2->val = min(t2->lf->val,t2->rg->val);
}

void out(Node* x){
	if(x->l==x->r)cout<<x->l<<" = " <<x->val<<endl;
	else{
		cout<<x->l<<" "<<x->r<<" "<<x->val<<endl;
		out(x->lf);
		out(x->rg);
	}
}
int main(){	
#ifdef LocalHost
	freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
#endif

	cin>>n;
	REP(i,n)scanf("%d",p+i),inv[p[i]]=i;

	root1 = buildTree(0,n-1);
	root2 = buildTree(0,n-1);


	REP(i,n){
		if(i%2==0) setVal(root1,i,p[i]);
		else setVal(root2,i,p[i]);
	}

	breaks.insert(n);
	REP(i,n/2){
		int v1 = getMin(root1,0,n-1);
		int pos_1 = inv[v1];

		int pos_2 = *breaks.lower_bound(pos_1);
		
		int v3 = getMin(root2,pos_1,pos_2-1);
		int pos_3 = inv[v3];
	
		setVal(root1,pos_1,inf);
		setVal(root2,pos_1,inf);
		setVal(root1,pos_3,inf);
		setVal(root2,pos_3,inf);

		breaks.insert(pos_3);
		breaks.insert(pos_1);

		if(pos_1==0 && pos_3==n-1)swap(root1,root2);
		else{
			swapTrees(root1,root2,pos_1,pos_3);
			//cout<<"!"<<pos_1<<' '<<pos_3<<endl;
			//puts("t1");out(root1);puts("t2");out(root2);
		}
		printf("%d %d ",v1,v3);
	}
	puts("");

#ifdef LocalHost
	printf("TIME: %.3lf\n",ld(clock())/CLOCKS_PER_SEC);
#endif
	return 0;
}

Measured memory_bytes: 49920