#include<bits/stdc++.h>

using namespace std;


const int maxi=2e6+6;


int t[2][maxi];
int a[maxi],b[maxi];
int len,n;
int p[maxi];
int rez[maxi];
set<int> st;
set<int>st1;

void build(int *a, int n, int tip)
{
    len=1<< int (ceil(log2(n)));

    //cout<<len<<"\n";
    for (int i=len;i<2*len;i++)
        t[tip][i]=1e9;

    for (int i=len;i<2*len;i++)
        if (i>len+n-1) t[tip][i]=1e9; else
        if (i%2==0 && tip==1) t[1][i]=a[i-len+1]; else
        if (i%2==1 && tip==0)
        t[0][i]=a[i-len+1];

    for (int i=len-1;i>0;i--)
        t[tip][i]=min(t[tip][i<<1],t[tip][i<<1|1]);
}


int get(int l, int r,int tip)
{
    int ans=a[l];

    l+=len-1;
    r+=len;

    for (;l<r;l>>=1,r>>=1){
        if (l&1) ans=min(ans,t[tip][l++]);
        if (r&1) ans=min(ans,t[tip][--r]);
    }
    return ans;
}


int main()
{

    cin>>n;

    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
         p[a[i]]=i;
    }

     build(a,n,0);
     build(a,n,1);

    st1.insert(0);
    st1.insert(n+1);

    st.insert(get(1,n,1));

    for (int i=1;i<=n;i+=2)
    {
        int cur=*st.begin();
        rez[i]=cur;
        int tip=(1-p[cur]%2);
        int idx=*st1.lower_bound(p[cur]);
        rez[i+1]=get(p[cur]+1,idx-1,tip);
        st.erase(cur);

        set<int>::iterator it=st1.lower_bound(p[cur]);
        it--;

        int ispod=*it;
        st1.insert(p[cur]);
        st1.insert(p[rez[i+1]]);

        if (p[cur]-ispod>1)
            st.insert(get(ispod+1,p[cur]-1,(ispod+1)%2));

         if (p[rez[i+1]]-p[cur]>1)
            st.insert(get(p[cur]+1,p[rez[i+1]]-1,(p[cur]+1)%2));

           if (idx-p[rez[i+1]]>1)
                st.insert(get(p[rez[i+1]]+1,idx-1,(p[rez[i+1]]+1)%2));

    }

  for (int i=1;i<=n;i++)
    printf("%d ",rez[i]);
  printf("\n");
   return 0;
}

//RINGISPIL SE PLACA