#include <cstdio>
#include <queue>

using namespace std;

struct Bounds {
    int lower, upper;
};

int a[2][500012];
int n;

FILE *inFile;
FILE *outFile;


void reverse_between(int *v, int lower, int upper)
{
    int mid = (lower + (upper - lower + 1) / 2);
    for (int j = lower; j < mid; ++j)
    {
        swap(v[j], v[lower + upper - j]);
    }
}

void read_and_split(int *v, int &n, queue <Bounds> &seq_queue)
{
    inFile = fopen ("algsort.in","r");

    int current, next, previous;
    bool increasing, changed = false;

    Bounds seq_bounds;
    seq_bounds.lower = 0;
    seq_bounds.upper = 0;


    fscanf(inFile, "%d", &n);
    fscanf(inFile, "%d %d", &current, &next);

    v[0] = current;
    v[1] = next;

    increasing = (current <= next);

    previous = next;
    seq_bounds.upper = 1;

    for (int i = 2; i < n; i++)
    {
        fscanf(inFile, "%d", &current);
        v[i] = current;

        if (changed == true)
        {
            increasing = (previous < current);
            changed = false;
        }

        if ((previous < current) == increasing)
        {
            ++seq_bounds.upper;
        }
        else
        {
            seq_queue.push(seq_bounds);

            if (increasing == false)
            {
                reverse_between(v, seq_bounds.lower, seq_bounds.upper);
            }

            changed = true;

            seq_bounds.lower = i;
            seq_bounds.upper = i;
        }

        previous = current;
    }

    seq_queue.push(seq_bounds);

    if (increasing == false)
    {
        reverse_between(v, seq_bounds.lower, n-1);
    }

    fclose(inFile);
}

void print_result(int *v, int n)
{
    outFile = fopen ("algsort.out", "w+");

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

    fclose(outFile);

}

int main()
{
    queue <Bounds> seq_queue;

    read_and_split(a[0], n, seq_queue);

    // Merging phase


    int len = seq_queue.size();
    int take = (len + 1) / 2;
    int merging_stage = 0;

    bool even = (len % 2 == 0);


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

        for (int i = 0; i < take; ++i)
        {
            // first-bounds - the bounds of the first seq
            // to be merged with the second seq (for which
            // we use second_bounds)
            Bounds first_bounds, second_bounds;

            first_bounds = seq_queue.front();
            seq_queue.pop();

            second_bounds = seq_queue.front();
            seq_queue.pop();

            Bounds new_seq;
            new_seq.lower = first_bounds.lower;
            new_seq.upper = second_bounds.upper;
            seq_queue.push(new_seq);

            int first_lower = first_bounds.lower;
            int first_upper = first_bounds.upper;

            int second_lower = second_bounds.lower;
            int second_upper = second_bounds.upper;

            int new_lower = first_lower;
            int new_upper = second_upper;

            for (int l = new_lower; l <= new_upper; ++l)
            {
                if (first_lower <= first_upper && second_lower <= second_upper)
                {
                    if (a[merging_stage % 2][first_lower] < a[merging_stage % 2][second_lower])
                    {
                        a[(merging_stage + 1) % 2][l] = a[merging_stage % 2][first_lower];
                        ++first_lower;
                    }
                    else
                    {
                        a[(merging_stage + 1) % 2][l] = a[merging_stage % 2][second_lower];
                        ++second_lower;
                    }
                }
                else
                {
                    if (first_lower > first_upper)
                    {
                        while (l <= new_upper)
                        {
                            a[(merging_stage + 1) % 2][l] = a[merging_stage % 2][second_lower];
                            ++second_lower;
                            ++l;
                        }
                    }
                    else
                    {
                        while (l <= new_upper)
                        {
                            a[(merging_stage + 1) % 2][l] = a[merging_stage % 2][first_lower];
                            ++first_lower;
                            ++l;
                        }
                    }
                }
            }
        }

        if (even == false)
        {
            Bounds remaining_seq = seq_queue.front();
            int lower_bound, upper_bound;
            lower_bound = remaining_seq.lower;
            upper_bound = remaining_seq.upper;
            for (lower_bound; lower_bound <= upper_bound; ++lower_bound)
                a[(merging_stage + 1) % 2][lower_bound] = a[merging_stage % 2][lower_bound];
            seq_queue.pop();
            seq_queue.push(remaining_seq);
        }

        len = seq_queue.size();
        take = (len + 1) / 2;

        even = (len % 2 == 0);

        ++merging_stage;
    }

    print_result(a[merging_stage % 2], n);

    return 0;
}