#include <cstdio>
#include <queue>

using namespace std;

struct Point {
    int lower, upper;
};

int a[2][500012];

int main()
{
    FILE * inFile, *outFile;

    inFile = fopen ("algsort.in","r");
    outFile = fopen ("algsort.out", "w+");

    int n, x, y, previous;
    fscanf(inFile, "%d", &n);


    queue <Point> sequence_queue;

    Point sequence_bounds;
    sequence_bounds.lower = 0;
    sequence_bounds.upper = 0;

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

        if ((previous < x) == poz)
        {
            ++sequence_bounds.upper;
        }
        else
        {
            sequence_queue.push(sequence_bounds);
            if (poz == false)
            {
                int mid = (sequence_bounds.lower + (sequence_bounds.upper  - sequence_bounds.lower + 1) / 2);
                for (int j = sequence_bounds.lower; j < mid; ++j)
                {
                    swap(a[0][j], a[0][sequence_bounds.lower + sequence_bounds.upper - j]);
                }
            }
            ch = true;
            sequence_bounds.lower = i;
            sequence_bounds.upper = i;
        }

        previous = x;
    }
    sequence_queue.push(sequence_bounds);
    if (poz == false)
    {
        for (int j = sequence_bounds.lower; j < (n + sequence_bounds.lower) / 2; ++j)
        {
            swap(a[0][j], a[0][n + sequence_bounds.lower - j - 1]);
        }
    }

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

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

    // Merging part
    int take = (len + 1) / 2;
    int times = 0;

    while (len != 1)
    {
        if (even == false)
            --take;

        for (int i = 0; i < take; ++i)
        {
            Point first_seq_bounds, second_seq_bounds;
            first_seq_bounds = sequence_queue.front();
            sequence_queue.pop();
            second_seq_bounds = sequence_queue.front();
            sequence_queue.pop();

            Point newP;
            newP.lower = first_seq_bounds.lower;
            newP.upper = second_seq_bounds.upper;
            sequence_queue.push(newP);

            int lb1 = first_seq_bounds.lower;
            int lb2 = second_seq_bounds.lower;
            int up1 = first_seq_bounds.upper;
            int up2 = second_seq_bounds.upper;
            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;
                        }
                    }
                }
            }
        }

        if (even == false)
        {
            Point remaining_sequence = sequence_queue.front();
            int lower_bound, upper_bound;
            lower_bound = remaining_sequence.lower;
            upper_bound = remaining_sequence.upper;
            for (lower_bound; lower_bound <= upper_bound; ++lower_bound)
                a[(times + 1) % 2][lower_bound] = a[times % 2][lower_bound];
            sequence_queue.pop();
            sequence_queue.push(remaining_sequence);
        }

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


    for (int i = 0; i < n; ++i)
        fprintf(outFile, "%d ", a[times % 2][i]);
    fprintf(outFile, "\n");

    return 0;
}