/**

Author: Dan Fodor. All rights reserved.

The problem: Sort an array of n numbers.

Input:
- first line: a number n (the number of numbers to be sorted)
- second line: n numbers

Output:
- first line: the sorted n numbers


Tested on GNU C++ compiler.

*/

#include <cstdio>
#include <queue>

using namespace std;

struct Point
{
    int first, last;
};

int a[2][500012];

FILE *in_file, *out_file;

void open_files(FILE *& read_file, FILE *& write_file)
{
    read_file = fopen ("algsort.in", "r");
    write_file = fopen ("algsort.out", "w+");
}
void close_files(FILE *& read_file, FILE *& write_file)
{
    fclose(read_file);
    fclose(write_file);
}

void output (int *sortedNumbers, int len)
{
    for (int i = 0; i < len; ++i)
        fprintf(out_file, "%d ", sortedNumbers[times % 2][i]);
    fprintf(out_file, "\n");
}

int main()
{

    open_files(in_file, out_file);

    int n, x, y, prev;

    fscanf(in_file, "%d", &n);

    if (n <= 2)
    {
        if (n == 1)
        {
            fscanf(in_file, "%d", &x);
            fprintf(out_file, "%d\n", x);
        }
        if (n == 2)
        {
            fscanf(in_file, "%d %d", &x, &y);
            fprintf(out_file, "%d %d", min(x, y), max(x, y));
        }
        return 0;
    }

    // if the array has size larger than 2
    queue <Point> q;

    Point p;
    p.first = 0;
    p.last = 0;

    bool poz, ch = false;
    fscanf(in_file, "%d %d", &x, &y);
    a[0][0] = x;
    a[0][1] = y;
    poz = true;
    if (x > y)
        poz = false;
    prev = y;
    p.last = 1;
    for (int i = 2; i < n; i++)
    {
        fscanf(in_file, "%d", &x);
        a[0][i] = x;
        if (ch == true)
        {
            poz = false;
            if (prev < x)
                poz = true;
            ch = false;
        }

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

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

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

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

    int take = (len + 1) / 2;
    int times = 0;
    //for (int l = 0; l < n; ++l)
    //    a[1][l] = a[0][l];


    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.first = p1.first;
            newP.last = p2.last;
            q.push(newP);

            int lb1 = p1.first;
            int lb2 = p2.first;
            int up1 = p1.last;
            int up2 = p2.last;
            int mini = lb1;
            int maxi = up2;

            for (int l = mini; l <= maxi; ++l)
            {
                if (lb1 <= up1 && lb2 <= up2)
                {
                    if (a[times % 2][lb1] < a[times % 2][lb2])
                    {
                        a[(times + 1) % 2][l] = a[times % 2][lb1];
                        ++lb1;
                    }
                    else
                    {
                        a[(times + 1) % 2][l] = a[times % 2][lb2];
                        ++lb2;
                    }
                }
                else
                {
                    if (lb1 > up1)
                    {
                        while (l <= maxi)
                        {
                            a[(times + 1) % 2][l] = a[times % 2][lb2];
                            ++lb2;
                            ++l;
                        }
                    }
                    else
                    {
                        while (l <= maxi)
                        {
                            a[(times + 1) % 2][l] = a[times % 2][lb1];
                            ++lb1;
                            ++l;
                        }
                    }
                }
            }
            //for (int l = mini; l <= maxi; ++l)
            //    a[0][l] = b[l];
        }
        if (even == false)
        {
            Point z = q.front();
            int in, stop;
            in = z.first;
            stop = z.last;
            for (in; in <= stop; ++in)
                a[(times + 1) % 2][in] = a[times % 2][in];
            q.pop();
            q.push(z);
        }

        len = q.size();
        take = (len + 1) / 2;
        even = true;
        if (len % 2 != 0)
            even = false;
        ++times;
    }


    output(a, n);


    // closing the files
    close_files(in_file, out_file);

    return 0;
}