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

struct Node {
    int freq = 0;
    int left = -1;
    int right = -1;
};

struct Code {
    long long code = -1;
    int len = -1;
};

struct Huffman {
    std::vector<Node> nodes;
    std::queue<unsigned> q1;
    std::queue<unsigned> q2;

    std::vector<Code> codes;

    unsigned queue_size() { return q1.size() + q2.size(); }

    unsigned pop_min_freq() {
        if (q1.empty()) {
            auto id = q2.front();
            q2.pop();
            return id;
        }
        if (q2.empty()) {
            auto id = q1.front();
            q1.pop();
            return id;
        }

        auto id1 = q1.front();
        auto id2 = q2.front();
        if (nodes.at(id1).freq <= nodes.at(id2).freq) {
            q1.pop();
            return id1;
        } else {
            q2.pop();
            return id2;
        }
    }

    void add_combined_node(int id1, int id2) {
        const auto &node1 = nodes.at(id1);
        const auto &node2 = nodes.at(id2);

        int new_id = nodes.size();
        Node new_node{node1.freq + node2.freq, id1, id2};
        nodes.push_back(new_node);

        q2.push(new_id);
    }

    long long traverse(int id, long long code, int code_len) {
        const auto &node = nodes.at(id);

        if (node.left == -1) {
            // Node is a leaf
            codes[id] = {code, code_len};
            return code_len * node.freq;
        } else {
            // Node is internal
            return traverse(node.left, (code << 1) + 0, code_len + 1) +
                   traverse(node.right, (code << 1) + 1, code_len + 1);
        }
    }

    long long traverse(int root_id) {
        const auto &node = nodes.at(root_id);
        return traverse(node.left, 0, 1) + traverse(node.right, 1, 1);
    }
};

int main() {
    std::ifstream ifs("huffman.in");
    int n;
    ifs >> n;

    Huffman huffman;

    for (int i = 0; i < n; i++) {
        int freq;
        ifs >> freq;
        Node node{freq, -1, -1};
        huffman.nodes.push_back(node);
        huffman.q1.push(i);
    }
    ifs.close();

    while (huffman.queue_size() > 1) {
        auto id1 = huffman.pop_min_freq();
        auto id2 = huffman.pop_min_freq();

        huffman.add_combined_node(id1, id2);
    }

    // Remaining node is the root
    auto root_id = huffman.pop_min_freq();

    huffman.codes.resize(n);
    auto compressed_len = huffman.traverse(root_id);

    std::ofstream ofs("huffman.out");
    ofs << compressed_len << '\n';

    for (int i = 0; i < n; i++) {
        const auto &node = huffman.codes.at(i);
        ofs << node.len << ' ' << node.code << '\n';
    }
    ofs.close();
    return 0;
}