#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>

//#define ONLINE_JUDGE

const int MAXN = 131072;
const int MAX_NODE_N = MAXN*2+1;
using namespace std;

struct Element
{
    int number;//number from input
    int index;//order from input
};

bool operator < (const Element &A, const Element &B)
{
    return A.number < B.number;//sort by num
}

Element num[MAXN];
int segTreeRMQ[MAX_NODE_N];

void readInputArr(int N)
{
    for(int i=0; i<N; i++)
    {
        num[i].index = i;
        scanf("%d",&num[i].number);
    }
}

#ifndef ONLINE_JUDGE
void testArr(int N)
{
    puts("-------------");
    puts("Test read : (num,index)");
    for(int i=0; i<N; i++)
        printf(" (%d,%d)", num[i].number, num[i].index);
    puts("\n-------------");
}
#endif // ONLINE_JUDGE
//referenece
//http://w...content-available-to-author-only...r.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static

//almost the same code, OMG
void initializeTree(int node_i, int b, int e, int M[MAX_NODE_N], Element A[MAXN], int N)
{
    if(b==e)
        M[node_i] = b;//position of min "index from input"
    else
    {
        //node_i : heap style
        initializeTree(2*node_i, b, (b+e)/2 , M, A, N);//init left
        initializeTree(2*node_i+1, (b+e)/2+1, e, M, A, N);//init right
        //b,e 1~N
        //Arr 0~N
        if(A[M[2*node_i]].index<=A[M[2*node_i+1]].index)
            M[node_i] = M[2*node_i];//choose left child min
        else
            M[node_i] = M[2*node_i+1];
    }

    //debug info
    #ifndef ONLINE_JUDGE
    printf("segT[%d][%d,%d]=%d, A[%d].index=%d\n",node_i, b, e, M[node_i], A[M[node_i]]);
    #endif // ONLINE_JUDGE
}

//i, j is query range i<=j
int query(int node_i, int b, int e, int M[MAX_NODE_N], Element A[MAXN], int i, int j)
{
    int p1, p2;

    //no intersection
    //A.lesser > B.greater or A.greater < B.lesser
    // [i,j]
    //
    //        [b,e]
    //--------------
    //         [i,j]
    // [b,e]
    if(i>e || j<b)
        return -1;//NULL

    //intersect, included
    // [i,           j]
    //       [b,e]
    if(b>=i&&e<=j)
        return M[node_i];

    //intersect, not include
    p1 = query(2*node_i, b, (b+e)/2, M, A, i, j);
    p2 = query(2*node_i+1, (b+e)/2+1, e, M, A, i, j);

    if(p1==-1)
        return p2;//M[node]=p2?
    if(p2==-1)
        return p1;

    if(A[p1].index<=A[p2].index)
        return p1;
    else
        return p2;

}

const int segTreeRootI = 1;
void fake_preorder_tra(int i, int j, int N, int M[MAX_NODE_N], Element A[MAXN])
{
    int rootPos = query(segTreeRootI, 0, N-1, M, A, i,j);//root
    if(rootPos>=0&&rootPos<N)
    {
        if(A[rootPos].index==0)
            printf("%d", A[rootPos].number);
        else
            printf(" %d", A[rootPos].number);


        if(i!=j)//not leave
        {
         //left
            fake_preorder_tra(i,rootPos-1, N, M, A);
        //right
            fake_preorder_tra(rootPos+1,j, N, M, A);
        }

    }
}

int main()
{
    int N;
    while(scanf("%d",&N)!=EOF)
    {
        readInputArr(N);

        //debug info
        #ifndef ONLINE_JUDGE
        testArr(N);
        #endif // ONLINE_JUDGE

        std::sort(num,num+N);//get Inorder traversal

        //debug info
        #ifndef ONLINE_JUDGE
        printf("sorted\n");
        testArr(N);
        #endif // ONLINE_JUDGE


        initializeTree(segTreeRootI,0,N-1,segTreeRMQ,num,N);
        fake_preorder_tra(0,N-1,N,segTreeRMQ,num);
        putchar('\n');
    }
    return 0;
}