#include <bits/stdc++.h>

#define PB          push_back
#define PF          push_front
#define MP          make_pair
#define FI          first
#define SE          second
#define SIZE( A )   int( ( A ).size( ) )
#define ALL( A )    ( A ).begin( ), ( A ).end( )
#define ALLR( A )   ( A ).rbegin( ), ( A ).rend( )

using namespace std;

typedef long long           ll;
typedef unsigned long long  ull;
typedef double              lf;
typedef pair< int, int >    pii;
typedef pair< ll, ll >      pll;
typedef vector< bool >      vb;
typedef vector< lf >        vd;
typedef vector< ll >        vll;
typedef vector< int >       vi;
typedef vector< pii >       vpii;

const int MAXN = int( 2e5 )+10;
const int MOD  = int( 360 );
const int oo   = INT_MAX;
const int LOG2 = 20;

int n, arr[ 2 ][ MAXN ], org[ MAXN ];
int st[ 2 ][ MAXN ][ LOG2 ];

void create_st() {
  for( int k = 0; k < 2; ++k ) {
    for( int i = 0; i < n; i++ ) {
      st[ k ][ i ][ 0 ] = i;
    }
    for( int j = 1; j < LOG2; j++ ) {
      for( int i = 0; i+(1<<(j-1)) < n; i++ ) {
        if( arr[ k ][ st[ k ][ i ][ j-1 ] ] < arr[ k ][ st[ k ][ i+(1<<(j-1)) ][ j-1 ] ] ) {
          st[ k ][ i ][ j ] = st[ k ][ i ][ j-1 ];
        }
        else {
          st[ k ][ i ][ j ] = st[ k ][ i+(1<<(j-1)) ][ j-1 ];
        }
      }
    }
  }
}

int query( int f, int t ) {
  int j = 31-__builtin_clz( t-f+1 );
  if( org[ st[ f%2 ][ f ][ j ] ] < org[ st[ f%2 ][ t-(1<<j)+1 ][ j ] ] ) {
    return st[ f%2 ][ f ][ j ];
  }
  return st[ f%2 ][ t-(1<<j)+1 ][ j ];
}

struct Interval {
  int l, r, mn;
  Interval() {}
  Interval( int l, int r ) : l( l ), r( r ), mn( query(l,r) ) {}
};

bool operator > ( const Interval &i1, const Interval &i2 ) {
  return org[ i1.mn ] < org[ i2.mn ];
}

bool operator < ( const Interval &i1, const Interval &i2 ) {
  return org[ i1.mn ] > org[ i2.mn ];
}

bool operator >= ( const Interval &i1, const Interval &i2 ) {
  return org[ i1.mn ] <= org[ i2.mn ];
}

bool operator <= ( const Interval &i1, const Interval &i2 ) {
  return org[ i1.mn ] >= org[ i2.mn ];
}


int main( ) {

  #ifdef LOCAL
    freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
  #else
    //freopen( "input", "r", stdin );
    //freopen( "output", "w", stdout );
    ios_base::sync_with_stdio( 0 );
    cin.tie( 0 );
  #endif
  while( cin >> n ) {
    for( int i = 0; i < n; ++i ) {
      cin >> org[ i ];
      arr[ i%2 ][ i ] = org[ i ];
      arr[ 1-(i%2) ][ i ] = oo;
    }

    create_st();
    priority_queue< Interval > pq;
    pq.push( Interval(0,n-1) );
    Interval cur;
    for( int i = 0, j; i < n; i += 2 ) {
      cur = pq.top(); pq.pop();
      cout << org[ cur.mn ] << " ";
      j = query( cur.mn+1, cur.r );
      cout << org[ j ] << " \n"[ i+2 == n ];
      //cout << cur.l << " " << cur.mn << " " << j << " " << cur.r << endl;
      if( cur.l < cur.mn-1 ) {
        pq.push( Interval( cur.l, cur.mn-1 ) );
        //cout << "---> " << cur.l << " " << cur.mn-1 << " " << query( cur.l, cur.mn-1 ) << endl;
      }
      if( cur.mn+1 < j-1 ) {
        pq.push( Interval( cur.mn+1, j-1 ) );
        //cout << "---> " << cur.mn+1 << " " << j-1 << " " << query( cur.mn+1, j-1 ) << endl;
      }
      if( j+1 < cur.r ) {
        pq.push( Interval( j+1, cur.r ) );
        //cout << "---> " << j+1 << " " << cur.r << " " << query( j+1, cur.r ) << endl;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 35704