#include<bits/stdc++.h>
using namespace std;  
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define rep(i,n) for(ll i=0;i<(n);i++)  
#define pii pair<int,int>
#define piii pair<int,pii>
#define mp make_pair
#define pb push_back  
#define ALL(a) (a).begin(),(a).end()
#define FST first
#define SEC second  
const int INF = (INT_MAX/2);
const ll LLINF = (LLONG_MAX/2);
const double eps = 1e-5;
const double PI = M_PI;  
#define DEB cerr<<"!"<<endl
#define SHOW(a,b) cerr<<(a)<<" "<<(b)<<endl
#define SHOWARRAY(ar,i,j) REP(a,i)REP(b,j)cerr<<ar[a][b]<<((b==j-1)?((a==i-1)?("\n\n"):("\n")):(" "))
  
#define DIV 1000000007
typedef vector<ll> Array;
typedef vector<Array> matrix;
typedef tuple<int,int,int> tiii;
#define mt make_tuple
 
class segtree{
public:
  int Node;
  vector<int> table;
  segtree(int);
  int ope(const int,const int);
  void update(int index,const int value){ // index is 0-indexed.
    index += Node;
    table[index] = value; // Check!
    while(index > 0){
      index /= 2;
      table[index] = ope(table[2*index],table[2*index+1]);
    }
  }
  int find(int l, int r);
};
int segtree::find(int l,int r){ // l,r is 0-indexed.
    if(l == r) return table[r+Node];
    l += Node; r += Node;
    int ans = 2147483647;  // Check!
    for(; l <= r;l >>=1, r >>=1){
      if(r == l){ans=ope(ans,table[l]); return ans;}
      if(r%2 == 0) ans=ope(ans,table[r]),--r;
      if(l%2) ans=ope(ans,table[l]),++l;
    }
    return ans;
}
 
segtree::segtree(int Max_Node){  // initialize
  Node = 2;
  while(Node < Max_Node)
    Node *= 2;
  table.resize(2*Node);
  for(int i = Node;i < Node*2; i++)
    table[i] = 2147483647; // initialize
  for(int i= Node-1; i > 0; i--)
    table[i] = ope(table[i*2],table[i*2+1]);
}
 
int segtree::ope(const int a,const int b){
  return min(a,b);
}
 
typedef tuple<int,int,bool> tiib; // l,r,%2
int main(){
  int n ; cin >> n;
  vi input(n);
  vi input_index(n+1);
  segtree st[2](n);
  rep(i,n){
    int in; cin >> in;
    input[i] = in;
    input_index[in] = i;
    if(i%2) st[1].update(i,in); else st[0].update(i,in);
  }
  auto c = [&](tiib a,tiib b){return st[get<2>(a)].find(get<0>(a),get<1>(a)) > st[get<2>(b)].find(get<0>(b),get<1>(b));};
  priority_queue<tiib,vector<tiib>,decltype(c)> q(c);  
  queue<int> ans;
 
  {
    int l = 0; int r = n-1; int b = 0;
    int l_index=input_index[st[b].find(l,r)], r_index=input_index[st[!b].find(l_index,r)];
    ans.push(l_index),ans.push(r_index);
    q.push(tiib{l,l_index-1,b});
    q.push(tiib{l_index+1,r_index-1,!b});
    q.push(tiib{r_index+1,r,b});
  }
  
  while(!q.empty()){
    tiib now = q.top(); q.pop();
    int l = get<0>(now); int r = get<1>(now); int b = get<2>(now);
    if(l >= r) continue; 
    int l_index=input_index[st[b].find(l,r)], r_index=input_index[st[!b].find(l_index,r)];
    ans.push(l_index),ans.push(r_index);
    if(l == r-1){continue;}
    q.push(tiib{l,l_index-1,b});
    q.push(tiib{l_index+1,r_index-1,!b});
    q.push(tiib{r_index+1,r,b});
  }
  
  while(!ans.empty()){
    int o = ans.front(); ans.pop();
    if(ans.empty())
      cout << input[o] << endl;
    else
      cout << input[o] << " ";
  }
  
  return 0;
}

Measured memory_bytes: 10904