#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

const int INF=1e9;
class SegmentTree{
public:

  int n;
  vector<int> tree;

  SegmentTree(){}

  SegmentTree(int size){
    n=1;
    while(n<size) n*=2;

    tree.resize(2*n-1,INF);
  }

  SegmentTree(vector<int> v){
    int vSize=v.size();
    n=1;
    while(n<vSize) n*=2;

    tree.resize(2*n-1,INF);

    for(int i=0;i<vSize;i++) tree[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--) tree[i]=min(tree[2*i+1],tree[2*i+2]);
  }

  void initialize(vector<int> v){
    int vSize=v.size();
    n=1;
    while(n<vSize) n*=2;

    tree.resize(2*n-1,INF);

    for(int i=0;i<vSize;i++) tree[i+n-1]=v[i];
    for(int i=n-2;i>=0;i--) tree[i]=min(tree[2*i+1],tree[2*i+2]);
  }

  void update(int index,int value){
    index+=n-1;

    tree[index]=value;
    while(index>0){
      index=(index-1)/2;
      tree[index]=min(tree[2*index+1],tree[2*index+2]);
    }
  }

  int getMin(int a,int b,int k=0,int l=0,int r=-1){//[a,b),getMin(a,b,0,0,-1)
    if(r<0) r=n;

    if(r<=a||b<=l) return INF;
    else if(a<=l&&r<=b) return tree[k];
    else{
      int lval=getMin(a,b,2*k+1,l,(l+r)/2);
      int rval=getMin(a,b,2*k+2,(l+r)/2,r);
      return min(lval,rval);
    }
  }
};


int N;
vector<int> P;

int trans[200020];
SegmentTree odd_seg,even_seg,seg;

pair<int,int> val[200020];
vector<int> g[200020];
int number;


void rec(int l,int r){//[l,r]  l%2!=r%2
  if(l+1==r){
      val[number++]=mkp(P[l],P[r]);
      return;
  }

  int left_val=INF;
  if(l%2){
      left_val=odd_seg.getMin(l,r+1);
      odd_seg.update(trans[left_val],INF);
  }else{
      left_val=even_seg.getMin(l,r+1);
      even_seg.update(trans[left_val],INF);
  }
  seg.update(trans[left_val],INF);

  int right_val=0;
  if(r%2){
      right_val=odd_seg.getMin(trans[left_val]+1,r+1);
      odd_seg.update(trans[right_val],INF);
  }else{
      right_val=even_seg.getMin(trans[left_val]+1,r+1);
      even_seg.update(trans[right_val],INF);
  }
  seg.update(trans[right_val],INF);
  
  int now=number;
  val[number++]=mkp(left_val,right_val);
  if(l<trans[left_val]){
      g[now].push_back(number);
      rec(l,trans[left_val]-1);
  }
  if(trans[right_val]-trans[left_val]+1>2){
      g[now].push_back(number);
      rec(trans[left_val]+1,trans[right_val]-1);
  }
  if(trans[right_val]<r){
      g[now].push_back(number);
      rec(trans[right_val]+1,r);
  }

  return;
}

int main(){
  cin>>N;
  P.resize(N);
  rep(i,N) cin>>P[i];

  rep(i,N) trans[P[i]]=i;
  vector<int> odd(N,INF),even(N,INF);
  rep(i,N){
      if(i%2) odd[i]=P[i];
      else even[i]=P[i];
  }

  odd_seg.initialize(odd);
  even_seg.initialize(even);
  seg.initialize(P);

  rec(0,N-1);

  map<pair<int,int>,int> mp;
  for(int i=0;i<number;i++) mp[val[i]]=i;

  vector<pair<int,int>> ans;
  priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> PQ;
  PQ.push(val[0]);
  
  while(!PQ.empty()){
      auto f=PQ.top();
      PQ.pop();

      ans.push_back(f);
      int now=mp[f];
      for(int i=0;i<g[now].size();i++) PQ.push(val[g[now][i]]);
  }

  for(int i=0;i<ans.size();i++){
      cout<<ans[i].first<<" "<<ans[i].second<<" ";
  }
  cout<<endl;

  return 0;
}


Measured memory_bytes: 40560