#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <queue>
#include <deque>
#include <iomanip>
#include <cmath>
#include <set>
#include <stack>
#include <map>
#include <unordered_map>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long 
//#define int long long
#define ld long double
#define vi deque<int>
#define pb push_back
#define ff first
#define ss second
#define ii pair<int,int>
#define iii pair<int,ii>
#define il pair<int,ll>
#define pll pair<ll,ll>
#define _path pair<ll,pair<ll,int> > 
#define vv deque
#define endl '\n'
#define mp make_pair

using namespace std;

#define ci pair<int,pair<char,int> > // length, character, id

const int MAXN = 2e5+5;

struct SegmentTree{
	ii st[4*MAXN];
	SegmentTree(){
		FOR(i,4*MAXN)st[i] = {MAXN,-1};
	}
	ii merge(ii a,ii b){
		if(a.ff < b.ff)return a;else return b;
	}
	void update(int node,int ss,int se,int i,int val){
		if(ss > i or i > se)return;
		if(ss == se){
			st[node] = {val,i};
		}else{
			int mid = (ss+se)/2;
			update(node*2+1,ss,mid,i,val);
			update(node*2+2,mid+1,se,i,val);
			st[node] = merge(st[node*2+1],st[node*2+2]);
		}
	}
	ii get(int node,int ss,int se,int l,int r){
		if(l > se or r < ss)return {MAXN,-1};
		if(l <= ss and se <= r)return st[node];
		int mid = (ss+se)/2;
		return merge(get(node*2+1,ss,mid,l,r),get(node*2+2,mid+1,se,l,r));
	}
} st[2];





int arr[MAXN];

set<ii>* merge(set<ii>* a,set<ii>* b){
	if(a->size() < b->size()){
		for(auto e: *a)b->insert(e);
		return b;
	}else{
		for(auto e: *b)a->insert(e);
		return a;
	}
	/*
	vv<ii> ans;
	while(!(a.empty() or b.empty())){
		if(a.front() < b.front()){
			ans.pb(a.front());a.pop_front();
		}else{
			ans.pb(b.front());b.pop_front();
		}
	}
	if(b.empty())swap(a,b);
	if(a.empty())for(auto e: b)ans.pb(e);
	return ans;*/
}

set<ii>* recurse(int left,int right,int id1,int id2){
	if(left >= right)return new set<ii>();
	cout << left << " " << right << endl;
	// find smallest on left;
	int mn = 0;
	/*FOR(i,right-left+1){
		if(i%2 == 0){
			if(arr[left + mn] > arr[left+i])mn = i;
		}
	}*/
	mn = st[id1].get(0,0,MAXN,left,right).ss;
	int mn2 = 0;
	/*FOR(j,right-left+1){
		if(right - j <= left + mn)break;
		if(j%2 == 0){
			if(arr[right-mn2] > arr[right-j])mn2 = j;
		}
	}*/
	mn2 = st[id2].get(0,0,MAXN,mn+1,right).ss;
	cout << mn << " " << mn2 << endl;
	//int x;cin >> x;
	//exit(0);
	// vv<ii> ans;
	// ans.pb({arr[mn],arr[mn2]});
	auto a = recurse(left,mn-1,id1,id2);
	auto b = recurse(mn+1,mn2-1,id2,id1);
	auto c = recurse(mn2+1,right,id1,id2);
	b = merge(b,c);
	a = merge(a,b);
	a->insert({arr[mn],arr[mn2]});
	return a;
}
#define data pair<pair<ii,ii>,pair<ii,ii> > // {mn,mn2},{left,right},{id1,id2};

ii getMins(ii a,ii id){
	int l = st[id.ff].get(0,0,MAXN,a.ff,a.ss).ss;
	//cout << l << endl;
	return {l,st[id.ss].get(0,0,MAXN,l+1,a.ss).ss};
}
ii invert(ii a){
	return {a.ss,a.ff};
}

void pr(ii a){
	cout << a.ff << " " << a.ss << endl;
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;
	FOR(i,n)cin >> arr[i];
	FOR(i,n){
		st[i%2].update(0,0,MAXN,i,arr[i]);
		//cout << i << " " << i%2 <<  " " << arr[i] << endl;
	}
	vv<ii> aa;

	priority_queue<data, vv<data>, greater<data> > pq;
	ii a = getMins({0,n-1},{0,1});
	pq.push({{{arr[a.ff],arr[a.ss]},a},{{0,n-1},{0,1}}});
	while(!pq.empty()){
		data item = pq.top();pq.pop();
		aa.pb(item.ff.ff);
		//pr(item.ff.ff);
		//pr(item.ss.ff);
		//cout << "=====" << endl;
		// left;
		//break;
		if(item.ss.ff.ff < item.ff.ss.ff-1){
			ii a1 = getMins({item.ss.ff.ff,item.ff.ss.ff-1},item.ss.ss);
			data d1 = {{{arr[a1.ff],arr[a1.ss]},a1},{{item.ss.ff.ff,item.ff.ss.ff-1},item.ss.ss}};
			pq.push(d1);
		}
		if(item.ff.ss.ff+1 < item.ff.ss.ss-1){
			ii a2 = getMins({item.ff.ss.ff+1,item.ff.ss.ss-1},invert(item.ss.ss));
			data d2 = {{{arr[a2.ff],arr[a2.ss]},a2},{{item.ff.ss.ff+1,item.ff.ss.ss-1},invert(item.ss.ss)}};	
			pq.push(d2);
		}
		if(item.ff.ss.ss+1 < item.ss.ff.ss){
			ii a3 = getMins({item.ff.ss.ss+1,item.ss.ff.ss},item.ss.ss);
			data d3 = {{{arr[a3.ff],arr[a3.ss]},a3},{{item.ff.ss.ss+1,item.ss.ff.ss},item.ss.ss}};
			pq.push(d3);			
		}
	}


	//auto ans = *recurse(0,n-1,0,1);
	for(auto e: aa){
		cout << e.ff << " " << e.ss << " ";
	}
	cout << endl;


	return 0;
}

Measured memory_bytes: 18444