#include<fstream>
#include<deque>
#include<vector>
#include<iostream>
using namespace std;
ifstream in ("algsort.in");
ofstream out ("algsort.out");
struct node {
    node *left, *right, *up;
    int value;
    node() {
        left = 0;
        right = 0;
        up = 0;
        value = 0;
    }
};
const int inf = 1e9 + 7;
vector<node*> all_nodes;
node* heap_top;
deque<node*> vacant; 
vector<node*> sorted_list;
void swap_in_list (node *a, node *b) {
    if (a->right == b) {
        b->left = a->left;
        a->left = b;
        b->right = a->right;
        a->right = b;
    }
    else if (b->right == a) {
        a->left = b->left;
        b->left = a;
        a->right = b->right;
        b->right = a;
    }
    else {
        swap (a->left, b->left);
        swap (a->right, b->right);
    }
}

void swap_in_heap (node *a, node *b) {
    if (a->up == b) {
        a->up = b->up;
        b->up = a;
        if (b->left == a) {
            b->left = a->left;
            a->left = b;
            swap (a->right, b->right);
        }
        else {
            b->right = a->right;
            a->right = b;
            swap (a->left, b->left);
        }
    }
    else if (b->up == a) {
        b->up = a->up;
        a->up = b;
        if (a->left == b) {
            a->left = b->left;
            b->left = a;
            swap (a->right, b->right);
        }
        else {
            a->right = b->right;
            b->right = a;
            swap (a->left, b->left);
        }
    }
    if (a != heap_top && (a->up->left == b || a->up->right == b)) {
        if (b == a->up->left) {
            a->up->left = a;
        }
        else {
            a->up->right = a;
        }
    }

    if (b != heap_top && (b->up->left == a  || b->up->right == a)) {
        if (a == b->up->left) {
            b->up->left = b;
        }
        else {
            b->up->right = b;
        }
    }

    if (a->left != 0) a->left->up = a;
    if (a->right != 0) a->right->up = a;
    if (b->left != 0) b->left->up = b;
    if (b->right != 0) b->right->up = b;
}

void up_in_heap (node *a) {
    while (a->up != 0 && a->up->value > a->value) {
        if (a->up == heap_top) {
            heap_top = a;
        }
        swap_in_heap (a, a->up);
    }
    return;
}

void down_in_heap (node *a) {
    while (a->left != 0) {
        if (a->right != 0 &&  a->left->value > a->right->value) {
            if (a->value > a->right->value) {
                if (a == heap_top) {
                    heap_top = a->right;
                }
                swap_in_heap (a, a->right);
            }
            else {
                break;
            }
        }
        else {
            if (a->value > a->left->value) {
                if (a == heap_top) {
                    heap_top = a->left;
                }
                swap_in_heap (a, a->left);
            }
            else {
                break;
            }
        }
    }
}

void add_in_heap (node *a) {
    if (vacant.empty()) {
        a->up = 0;
        heap_top = a;
    }
    else {
        if (vacant.front()->left == 0) {
            vacant.front()->left = a;
            a->up = vacant.front();
        }
        else if (vacant.front()->right == 0) {
            vacant.front()->right = a;
            a->up = vacant.front();
            vacant.pop_front();
        }
        else {
            vacant.pop_front();
        }
    }
    a->right = 0;
    a->left = 0;
    vacant.push_back (a);
}

void correct_heap () {
    for (int i = 0; i < all_nodes.size(); i ++) {
        up_in_heap (all_nodes[i]);
    }
}

node* last_added;
node* first_node;
node* final_node;
bool first;

bool take_from_heap () {
    if (heap_top->value == inf) {
        final_node = last_added;
        return false;
    }
    out << heap_top->value <<" ";
    heap_top->value = inf;
    down_in_heap (heap_top);
    return true;
}

int main (void) {
    first = true;
    int n;
    in >> n;
    node *former_node;
    for (int i = 1; i <= n; i ++) {
        int x;
        in >> x;
        node *aux = new node;
        aux->value = x;
        add_in_heap (aux);
        all_nodes.push_back(aux);
    }

    correct_heap();

    while (true) {
        bool keep_going = take_from_heap();
        if (!keep_going ) {
            break;
        }
    }

    return 0;
}