#include <list>
#include <ostream>
#include <fstream>
#include <vector>
#include <iostream>
#include <algorithm>

class BinomialHeap {
public:
    struct Node {
        long long value, degree;
        Node *child, *sibling, *parent;
    };

private:
    static bool cmp(Node*, Node*);
    std::list <Node*> roots;


public:
    void print(std::ostream&) const;
    static void printTree(std::ostream&, Node*);
    static Node* newNode(long long value);
    static Node* mergeTrees(Node*, Node*);

    void insertTree(Node*);
    void unionHeap(std::list <Node*>);
    void unionHeap(const BinomialHeap& );

    void addValue(long long);

    long long getMin() const;
    void deleteMin();
    bool empty() const;

    ~BinomialHeap();
};


void BinomialHeap::print(std::ostream &out) const{
    for(auto& it: this->roots) {
        BinomialHeap::printTree(out, it);
    }

}

void BinomialHeap::printTree(std::ostream &out, Node *node) {
    out << node->value << " " << node->degree << '\n';
    Node *it = node->child;
    while(it != nullptr) {
        BinomialHeap::printTree(out, it);
        it = it->sibling;
    }
}

BinomialHeap::Node *BinomialHeap::newNode(long long value) {
    Node *temp = new Node;
    temp->value = value;
    temp->degree = 0;
    temp->child = nullptr;
    temp->sibling = nullptr;
    temp->parent = nullptr;
    return temp;
}

BinomialHeap::Node *BinomialHeap::mergeTrees(BinomialHeap::Node *a, BinomialHeap::Node *b) {
    if(a->degree != b->degree) {
        std::cout << "not ok\n";
    }
    if(a->value < b->value) {
        std::swap(a, b);
    }
    a->sibling = b->child;
    a->parent = b;
    b->child = a;
    b->degree ++;

    return b;
}

void BinomialHeap::unionHeap(std::list<Node *> heap) {
    std::list <Node*> temp;
    std::list<Node*>::iterator i;
    std::list<Node*>::iterator j;
    i = this->roots.begin();
    j = heap.begin();

    Node* carry = nullptr;

    while(i != this->roots.end() and j != heap.end()){
        if(carry != nullptr) {
            if((*i)->degree == (*j)->degree and carry->degree) {
                temp.push_back(carry);
                carry = nullptr;
            }
            else if((*i)->degree == carry->degree) {
                carry = BinomialHeap::mergeTrees(*i, carry);
                i ++;
            }
            else if((*j)->degree == carry->degree) {
                carry = BinomialHeap::mergeTrees(*j, carry);
                j ++;
            }
            else {
                temp.push_back(carry);
                carry = nullptr;
            }
            continue;
        }

        if((*i)->degree == (*j)->degree) {
            carry = BinomialHeap::mergeTrees(*i, *j);
            i ++;
            j ++;
        }
        else if((*i)->degree < (*j)->degree) {
            temp.push_back(*i);
            i ++;
        }
        else {
            temp.push_back(*j);
            j ++;
        }
    }


    while(i != this->roots.end()) {
        if(carry != nullptr and (*i)->degree == carry->degree) {
            carry = BinomialHeap::mergeTrees(*i, carry);
            i ++;
        }
        else if(carry != nullptr) {
            temp.push_back(carry);
            carry = nullptr;
        }
        else {
            temp.push_back(*i);
            i ++;
        }
    }

    while(j != heap.end()) {
        if(carry != nullptr and (*j)->degree == carry->degree) {
            carry = BinomialHeap::mergeTrees(*j, carry);
            j ++;
        }
        else if(carry != nullptr) {
            temp.push_back(carry);
            carry = nullptr;
        }
        else {
            temp.push_back(*j);
            j ++;
        }
    }
    if(carry != nullptr) {
        temp.push_back(carry);
        carry = nullptr;
    }
    this->roots = temp;
//    for(auto it: this->roots) {
//        std::cout << it->degree << ' ';
//    }
//    std::cout << '\n';
}

void BinomialHeap::insertTree(BinomialHeap::Node *node) {
    std::list <Node*> temp;
    temp.push_back(node);
    this->unionHeap(temp);

}

void BinomialHeap::addValue(long long value) {
//    std::cout << "add\n";
    this->insertTree(BinomialHeap::newNode(value));
}

long long BinomialHeap::getMin() const {
    long long temp = INT64_MAX;
    for(auto& it: this->roots) {
        temp = std::min(temp, it->value);
    }
    return temp;
}



void BinomialHeap::deleteMin() {
//    std::cout << "delete\n";
    std::list <Node*> temp;
    long long min = this->getMin();
    Node* node = nullptr;
    for(auto& it: this->roots) {
        if(it->value == min) {
            node = it;
            this->roots.remove(it);
            break;
        }
    }

    if(node == nullptr) {
        return;
    }
//    int prevSize = 101;
//    int currentSize = 100;
    Node *it = node->child;
    while(it != nullptr) {
        temp.push_back(it);
//        prevSize = currentSize;
//        currentSize = it->degree;
//        if(prevSize <= currentSize) {
//            std::cout << "not ok\n";
//        }
        it = it->sibling;
    }
    std::reverse(temp.begin(), temp.end());
//    for(auto it: temp) {
//        std::cout << it->degree << ' ';
//    }
//    std::cout << '\n';

    this->unionHeap(temp);
}

bool BinomialHeap::empty() const {
    return this->roots.empty();
}

void BinomialHeap::unionHeap(const BinomialHeap& heap) {
    this->unionHeap(heap.roots);
}

BinomialHeap::~BinomialHeap() {
    for(auto &it: this->roots) {
        if(it != nullptr) {
            delete it;
            it = nullptr;
        }
    }
}

bool BinomialHeap::cmp(BinomialHeap::Node *a, BinomialHeap::Node *b) {
    return a->degree <= b->degree;
}

int main() {
    std::ifstream fin("algsort.in");
    std::ofstream fout("algsort.out");

    BinomialHeap heap;

    int n;
    fin >> n;
    std::vector <long long> in;
    for(int i = 0; i < n; i ++) {
        int temp;
        fin >> temp;
        in.push_back(temp);
        heap.addValue(temp);

    }
    std::vector <long long> v;
    while(!heap.empty()) {
        v.push_back(heap.getMin());
        fout << heap.getMin() << ' ';
        heap.deleteMin();
    }
    std::sort(in.begin(), in.end());
    for(int i = 1; i < v.size();i  ++) {
        if(v[i-1] > v[i]) {
            std::cout << i << ' ' << v[i-1] << ' ' << v[i] << '\n';
        }
    }
//    std::cout << v.size() << ' ' << in.size() << '\n';
    for(int i = 0; i < v.size(); i ++) {
        if(in[i] != v[i]) {
            std::cout << i << ' ' << in[i] << ' ' << v[i] << '\n';
        }
    }
    return 0;
}