/// c.cpp
# include <stdio.h>
# include <bits/stdc++.h>
using namespace std;
const pair < int , int > DD[] = {{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
# define fi cin
# define fo cout
# define x first
# define y second
# define ll long long
# define IOS ios_base :: sync_with_stdio(0);cin.tie(0)
# define p(v) cerr << #v << " = " << v << '\n'
# define p2(v) cerr << #v << " = " << (complex < decltype(v.x) > (v.x,v.y)) << '\n'
# define vi vector < int >
# define vl vector < ll >
# define pll pair < ll , ll >
# define pii pair < int , int >
# define mp make_pair
# define db long double
# define fail puts("-1")
# define yes puts("YES")
# define no puts("NO")
# define PP puts("Possible")
# define II puts("Impossible")
# define vii vector < pii >
# define vll vector < pll >
# define pb push_back
# define pdd pair < db , db >
# define all(s) s.begin(),s.end()
template < class T > T smin(T &a,T b) {if (a > b) a = b;return a;}
template < class T > T smax(T &a,T b) {if (a < b) a = b;return a;}
int main(void)
{
    #ifdef CF
    freopen("input","r",stdin);
    #endif // CF
    srand(time(0));
    fo << fixed << setprecision(7);
    cerr << fixed << setprecision(7);
    int n;
    fi>>n;
    static int p[1 << 20];
    static int q[1 << 20];
    for (int i = 1;i <= n;++i)
        fi>>p[i],q[p[i]] = i;
    static int D1[18][1 << 18];
    static int D2[18][1 << 18];
    for (int i = 1;i <= n;i += 2)
        D1[0][i] = i,D2[0][i] = -1;
    for (int i = 2;i <= n;i += 2)
        D2[0][i] = i,D1[0][i] = -1;
    auto Merge = [&](int a,int b)
    {
        if (min(a,b) == -1)
            return max(a,b);
        if (p[a] < p[b])
            return a;
        else
            return b;
    };
    for (int t = 1;t < 18;++t)
        for (int i = 1;i + (1 << t) <= n + 1;++i)
            D1[t][i] = Merge(D1[t - 1][i],D1[t - 1][i + (1 << (t - 1))]),
            D2[t][i] = Merge(D2[t - 1][i],D2[t - 1][i + (1 << (t - 1))]);
    static int Log[1 << 20];
    for (int i = 2;i <= n;++i)
        Log[i] = Log[i / 2] + 1;
    auto get1 = [&](int l,int r)
    {
        int k = Log[r - l + 1];
        return Merge(D1[k][l],D1[k][r - (1 << k) + 1]);
    };
    auto get2 = [&](int l,int r)
    {
        int k = Log[r - l + 1];
        return Merge(D2[k][l],D2[k][r - (1 << k) + 1]);
    };
    set < pair < int , pii > > ss;
    ss.insert(mp(p[get1(1,n)],mp(1,n)));
    vi ans;
    for (int cs = 0;2 * cs < n;++cs)
    {
        int pos = q[ss.begin()->x];
        int l = ss.begin()->y.x;
        int r = ss.begin()->y.y;
        ss.erase(ss.begin());
        if (l + 1 < pos)
        {
            if (l & 1)
                ss.insert(mp(p[get1(l,pos - 1)],mp(l,pos - 1)));
            else
                ss.insert(mp(p[get2(l,pos - 1)],mp(l,pos - 1)));
        }
        int nxt = -1;
        if (pos & 1)
            nxt = get2(pos,r);
        else
            nxt = get1(pos,r);
        ans.pb(p[pos]);
        ans.pb(p[nxt]);
        if (pos + 1 < nxt - 1)
        {
            if (pos & 1)
                ss.insert(mp(p[get2(pos + 1,nxt - 1)],mp(pos + 1,nxt - 1)));
            else
                ss.insert(mp(p[get1(pos + 1,nxt - 1)],mp(pos + 1,nxt - 1)));
        }
        if (nxt + 1 < r)
        {
            if (nxt & 1)
                ss.insert(mp(p[get2(nxt + 1,r)],mp(nxt + 1,r)));
            else
                ss.insert(mp(p[get1(nxt + 1,r)],mp(nxt + 1,r)));
        }
    }
    for (int i = 0;i < n;++i)
        fo << ans[i] << " \n"[i == n - 1];
    cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}


Measured memory_bytes: 46580