#include <fstream>
#include <queue>

using namespace std;

struct Point {
    int start, fin;
};

int a[500012];

int main()
{
    ifstream cin ("algsort.in");
    ofstream cout ("algsort.out");

    int n, x, y, prev;
    cin >> n;
    if (n <= 2)
    {
        if (n == 1)
        {
            cin >> x;
            cout << x << "\n";
        }
        if (n == 2)
        {
            cin >> x >> y;
            cout << min(x, y) << " " << max(x, y) << "\n";
        }
    }
    else
    {
        queue <Point> q;

        Point p;
        p.start = 0;
        p.fin = 0;

        int beg = 0;
        bool poz, ch = false;
        cin >> x >> y;
        a[0] = x;
        a[1] = y;
        poz = true;
        if (x > y)
            poz = false;
        prev = y;
        p.fin = 1;
        for (int i = 2; i < n; i++)
        {
            cin >> x;
            a[i] = x;
            if (ch == true)
            {
                poz = false;
                if (prev < x)
                    poz = true;
                ch = false;
            }

            if ((prev < x) == poz)
            {
                ++p.fin;
            }
            else
            {
                q.push(p);
                if (poz == false)
                {
                    int finish = (p.start + (p.fin  - p.start + 1) / 2);
                    for (int j = p.start; j < finish; ++j)
                    {
                        swap(a[j], a[finish + p.start - j]);
                    }
                }
                beg = i;
                ch = true;
                p.start = i;
                p.fin = i;
            }

            prev = x;
        }
        q.push(p);
        if (poz == false)
        {
            for (int j = beg; j < (n + beg) / 2; ++j)
            {
                swap(a[j], a[n + beg - j - 1]);
            }
        }

/*
        for (int i = 0; i < n; ++i)
            cout << a[i] << " ";
        cout << "\n";
        int l = 0,sz = q.size();
        while (l < sz)
        {
            ++l;
            Point z = q.front();
            q.pop();
            q.push(z);
            cout << z.start << " " << z.fin << "  ";
        }*/

        bool even = true;
        int len = q.size();

        if (len % 2 != 0)
            even = false;

        int take = (len + 1) / 2;

        while (len != 1)
        {
            if (even == false)
                --take;
            for (int i = 0; i < take; ++i)
            {
                Point p1, p2;
                p1 = q.front();
                q.pop();
                p2 = q.front();
                q.pop();

                Point newP;
                newP.start = p1.start;
                newP.fin = p2.fin;
                q.push(newP);

                int lb1 = p1.start;
                int lb2 = p2.start;
                int up2 = p2.fin;
                for (lb2; lb2 <= up2; ++lb2)
                {
                    int j = lb2;
                    while (lb1 <= (j - 1) && a[j - 1] > a[j])
                    {
                        swap (a[j-1], a[j]);
                        --j;
                    }
                }
            }
            if (even == false)
            {
                Point z = q.front();
                q.pop();
                q.push(z);
            }

            len = q.size();
            take = (len + 1) / 2;
            even = true;
            if (len % 2 != 0)
                even = false;
        }
        for (int i = 0; i < n; ++i)
            cout << a[i] << " ";
        cout << "\n";

    }

    return 0;
}