#include <iostream>
#include <fstream>
#include <vector>
#include <queue>


using namespace std;

struct comparator1 {
    bool operator()(int i, int j) {
        return i > j;
    }
};

struct Node {

    string code;
    int value;
    Node * left;
    Node * right;

    // компаратор
    bool operator() (const Node& x, const Node& y) const {
        return x.value > y.value;
    }

    // конструктор по умолчанию нужен для создания объекта-компаратора
    Node (int value = 0, Node * left = nullptr, Node * right = nullptr) {
        this->value = value; // множество символом узла
        this->code = ""; // строковое представление битового кода узла
        this->left = left; // левый ребенок
        this->right = right; // правый ребенок
    }

    Node (const Node& cnode) {
        this->value = cnode.value; // множество символом узла
        this->code = cnode.code; // строковое представление битового кода узла
        this->left = cnode.left; // левый ребенок
        this->right = cnode.right; // правый ребенок
    }

    //  объединение деревьев
    Node join (Node *x) {
        return *new Node(x->value + value, x, this);
    }

    void traversal_code(string code) {
        this->code = code;
        if (left != nullptr || right != nullptr) {
            left->traversal_code(code + "1");
            right->traversal_code(code + "0");
        }
    }

};


class Huffman
{
public:

    std::vector<string> codes;
    priority_queue<Node, std::vector<Node>, Node> tree;
    std::vector<Node> nodesWithCodes;

    Node root;


    void build()
    {
        // запускает алгоритм (после того как были добавлены все элементы)
        while (tree.size() > 1) {
            Node n1 = tree.top();
            tree.pop();
            Node n2 = tree.top();
            Node node = n1.join(n2);
            tree.push(node);
            tree.pop();
        }

        root = tree.top();
        root.traversal_code("");

    }

    void addChance(int chance)
    {
        // добавляет элемент в список (дерево, все зависит от реализации)
        nodesWithCodes.push_back(*new Node(chance));
        tree.push(nodesWithCodes[nodesWithCodes.size()-1]);

        codes.resize(nodesWithCodes.size());

    }

    string get(int i)
    {
        // выдает битовый код i символа
        return nodesWithCodes[i].code;
    }

};


int main()
{

    int n;
    Huffman *huff = new Huffman();
    fstream fin;
    fin.open("/Users/Margarita/CLionProjects/HT3/input.txt", ios::in);
    if (fin.is_open())
    {
        fin >> n;
        for (int i = 0; i < n; i++)
        {
            int x;
            fin >> x;
            huff->addChance(x);
        }

        fin.close();

        huff->build();
        fstream fout;
        fout.open("/Users/Margarita/CLionProjects/HT3/output.txt", ios::out);
        for (int i = 0; i < n; i++)
        {
            fout << huff->get(i) << (i == n - 1 ? "" : " ");
        }
        fout.close();
        delete huff;

    }

    return 0;

}