#include <fstream>
#include <cstdint>
#include <vector>
#include <queue>
#include <functional>
#include <unordered_map>

struct Huffman {
    struct Encoding {
        uint64_t val;
        uint32_t len;
    };
    using FrequencyType = uint64_t;
    using ElementType = uint32_t;
    using EncodingType = Encoding;
    struct Node {
        struct Children {
            uint32_t left;
            uint32_t right;
        };
        enum class NodeType {
            Regular,
            Leaf
        };

        FrequencyType freq : 60;
        NodeType type : 4;
                union {
            Children children;
            ElementType leafValue;
        };
        
        Node(FrequencyType freq)
        : freq(freq), type(NodeType::Regular), children({0, 0}) {}
        Node(FrequencyType freq, ElementType element)
        : freq(freq), type(NodeType::Leaf), leafValue(element) {}
    };
private:

    uint64_t numCharacters;
    std::vector<EncodingType> encodings;
    uint64_t totalLength;

    Huffman(uint64_t numCharacters) : numCharacters(numCharacters) {
        encodings.reserve(numCharacters);
    }
    static void Traverse(Huffman& h, const Node* node,const std::vector<Node>& nodes, uint64_t currMask, uint32_t height) {
        if (node->type == Node::NodeType::Leaf) {
            h.encodings[node->leafValue] = Encoding{currMask, height};
            h.totalLength += height * node->freq;
        } else {
            Traverse(h, &nodes[node->children.left], nodes, currMask << 1, height + 1);
            Traverse(h, &nodes[node->children.right], nodes, (currMask << 1) | 1, height + 1);
        }
    }
public:
    uint64_t NumCharacters() const { return numCharacters; }
    uint64_t TotalLength() const { return totalLength; }
    EncodingType EncodingFor(ElementType el) const { return encodings[el]; }
    static Huffman Construct(std::ifstream& f) {
        std::vector<Node> nodes;
        Node* root = nullptr;
        uint64_t numNodes;
        uint64_t qIdx = 0;
        f >> numNodes;
        nodes.reserve(2 * numNodes);

        std::vector<Node*> q;
        q.reserve(2 + numNodes / 2);

        Huffman h{numNodes};

        auto newNode = [&](FrequencyType freq) -> Node* {
            nodes.emplace_back(freq);
            return &nodes.back();
        };
        auto newLeaf = [&](FrequencyType freq, ElementType element) -> Node* {
            nodes.emplace_back(freq, element);
            return &nodes.back();
        };
        uint64_t currIdx = 0;
        Node* lastReadNode = nullptr;
        auto readNode = [&]() -> void {
            if (currIdx >= numNodes) {
                lastReadNode = nullptr;
                return;
            }
            uint64_t freq;
            f >> freq;
            lastReadNode = newLeaf(freq, currIdx++);
        };
        readNode();
        auto popReadNode = [&]() -> Node* {
            auto ret = lastReadNode;
            readNode();
            return ret;
        };

        auto qEmpty = [&] () -> bool {
            return q.size() == qIdx;
        };

        auto qFront = [&] () -> Node* {
            return q[qIdx];
        };

        auto popQueue = [&] () -> Node* {
            if (qEmpty()) {
                q.clear();
                qIdx = 0;
                return nullptr;
            }
            return q[qIdx++];
        };

        auto popNode = [&]() -> Node* {
            if (!lastReadNode) {
                if (qEmpty()) {
                    return nullptr;
                }
                return popQueue();
            }
            if (qEmpty()) {
                return popReadNode();
            }
            if (lastReadNode->freq < qFront()->freq) {
                return popReadNode();
            }
            return popQueue();
        };

        while (true) {
            Node* left = popNode();
            Node* right = popNode();
            if (!right) {
                root = left;
                break;
            }
            Node* n = newNode(left->freq + right->freq);
            n->children.left = left - nodes.data();
            n->children.right = right - nodes.data();
            q.push_back(n);
        }
        Traverse(h, root, nodes, 0u, 0);
        return h;
    }
};

int main() {
    std::ifstream fin("huffman.in");
    Huffman h = Huffman::Construct(fin);
    std::ofstream fout("huffman.out");
    fout << h.TotalLength() << '\n';
    for (uint32_t i = 0; i < h.NumCharacters(); ++i) {
        const auto encoding = h.EncodingFor(i);
        fout << encoding.len << ' ' << encoding.val << '\n';
    }
    return 0;
}