//Patience-LIS
//O(n log n)
/*#include<stdio.h>
#include<iostream>
#include<fstream>
#include<string.h>
#define nmax 100001
using namespace std;

int v[nmax],pachet[nmax],pred[nmax],ind[nmax];
int n;

ofstream fout("scmax.out");

void read()
{
    ifstream fin("scmax.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    memset(pachet,-1,sizeof(pachet));
    memset(pred,-1,sizeof(pred));
    memset(ind,-1,sizeof(ind));
    pachet[1]=v[1];
    ind[1]=1;
    fin.close();

}

int bs(int pos,int last)
{
    int st=1,dr=last,mid,x=v[pos],sol=-1,ok=0;
    while(st<=dr )
    {
        if(st==dr) if(x<=pachet[st]) return st;
        mid=(st+dr)/2;
        //cout<<pachet[mid]<<' '<<x<<endl;
        //if(x==pachet[mid]) ok=1;
        if(x<=pachet[mid])
        {
            sol=mid;
            dr=mid;
        }
        else
            st=mid+1;
    }
    //if(ok==1) return 0;
    return sol;

}

void afisare(int i)
{
    if(i>0)
    {
        afisare(pred[i]);
        fout<<v[i]<<' ';
    }
}


void solve()
{
    int i,j,x,nr_pachete=1,last_added=v[1];
    for(i=2;i<=n;i++)
    {
        //cout<<nr_pachete;
        if(v[i]==pachet[nr_pachete]) continue;
        if(v[i]>pachet[nr_pachete])
        {
            pachet[++nr_pachete]=v[i];
            //last_added=v[i];
            pred[i]=ind[nr_pachete-1];
            ind[nr_pachete]=i;
        }
        else
            if(v[i]<=pachet[1])
            {pachet[1]=v[i];
            //last_added=pachet[1];
            ind[1]=i;
            }
        else
        { x=bs(i,nr_pachete);
        //cout<<v[i]<<' '<<x<<endl;
        //cel mai din stanga pachet corespunzator
        pachet[x]=v[i];
        pred[i]=ind[x-1];
        ind[x]=i;
        //schimb fata pachetului cu primul element(cel vizibil din jocul de carti)
        //pred[v[i]]=pachet[x-1];
        }
    }

    fout<<nr_pachete<<'\n';
    x=ind[nr_pachete];
    afisare(x);
    fout.close();

}


int main()
{
    read();
    solve();
}*/

//Patience Sort
//O(2n log n)
#include<bits/stdc++.h>
#define nmax 100005
using namespace std;

int v[nmax],pachet[nmax],ind[nmax];
int n;

struct compare
{
    bool operator() (int x,int y)
    {
        return x>y;
    };
};

priority_queue<int, vector<int> ,compare> pq;
stack<int> S[nmax];
//S ca un stack

void read()
{
    ifstream fin("algsort.in");
    fin>>n;
    for(int i=1;i<=n;i++)
        fin>>v[i];
    memset(pachet,-1,sizeof(pachet));
    memset(ind,-1,sizeof(ind));
    ind[v[1]]=1;
    S[1].push(v[1]);
    fin.close();

}

int bs(int pos,int last)
{
    int st=1,dr=last,mid,x=v[pos],sol=-1,ok=0;
    while(st<=dr )
    {
        if(st==dr) if(x<=pachet[st]) return st;
        mid=(st+dr)/2;
        //cout<<pachet[mid]<<' '<<x<<endl;
        //if(x==pachet[mid]) ok=1;
        if(x<=pachet[mid])
        {
            sol=mid;
            dr=mid;
        }
        else
            st=mid+1;
    }
    //if(ok==1) return 0;
    return sol;

}


void solve()
{
    int i,j,x,nr_pachete=1,last_added=v[1];
    for(i=2;i<=n;i++)
    {
        //cout<<nr_pachete;
        if(v[i]==pachet[nr_pachete])
        {
            S[nr_pachete].push(v[i]);
            ind[v[i]]=nr_pachete;
        }
        if(v[i]>pachet[nr_pachete])
        {
            pachet[++nr_pachete]=v[i];
            S[nr_pachete].push(v[i]);
            ind[v[i]]=nr_pachete;
            //last_added=v[i];
            //pred[i]=ind[nr_pachete-1];
            //ind[nr_pachete]=i;
        }
        else
            if(v[i]<=pachet[1])
            {pachet[1]=v[i];
            //last_added=pachet[1];
            //ind[1]=i;
            S[1].push(v[i]);
            ind[v[i]]=1;
            }
        else
        { x=bs(i,nr_pachete);
        //cout<<v[i]<<' '<<x<<endl;
        //cel mai din stanga pachet corespunzator
        pachet[x]=v[i];
        S[x].push(v[i]);
        //pred[i]=ind[x-1];
        ind[v[i]]=x;
        //schimb fata pachetului cu primul element(cel vizibil din jocul de carti)
        //pred[v[i]]=pachet[x-1];
        }
    }

    //cout<<nr_pachete<<'\n';
    //x=ind[nr_pachete];
    //afisare(x);
    ofstream fout("algsort.out");

    for(i=1;i<=nr_pachete;i++)
        {pq.push(S[i].top());
        //cout<<S[i].top()<<' ';
        S[i].pop();
        }
    while(!pq.empty())
    {
        //cout<<pq.size();
        fout<<pq.top()<<' ';
        j=ind[pq.top()];
        //cout<<j<<' ';
        pq.pop();
        if(!S[j].empty()) pq.push(S[j].top());
        S[j].pop();

    }
    fout.close();


}


int main()
{
    read();
    solve();
}