#include <list>
#include <unordered_map>
#include <algorithm>
#include <vector>
#include <fstream>
#include <numeric>
#include <memory>

struct HuffmanEncoder {
    struct HuffmanNode {
        uint64_t frequency;
        const HuffmanNode* zero;
        const HuffmanNode* one;
    };
    struct Encoding {
        uint64_t code = 0;
        uint8_t length = 0;
        uint32_t frequency = 0;
    };
    uint64_t totalLength;
    std::vector<Encoding> encodings;
    static void traverse(uint64_t code, uint8_t length, const HuffmanNode* node, const std::unordered_map<const HuffmanNode*, int> dict, HuffmanEncoder& encoder) {
        if (node->zero != nullptr) {
            traverse(code << 1, length+1, node->zero, dict, encoder);
        }
        if (node->one != nullptr) {
            traverse((code << 1) | 1, length + 1, node->one, dict, encoder);
        }
        if ((node->zero == node->one) && (node->zero == nullptr)) {
            const auto idx = dict.find(node)->second;
            encoder.encodings[idx].code = code;
            encoder.encodings[idx].length = length;
        }
    }
    template<typename T>
    static HuffmanEncoder fromStream(T& stream) {
        int n;
        stream >> n;
        HuffmanEncoder encoder;
        encoder.encodings.resize(n);
        std::list<HuffmanNode> nodes;
        std::unordered_map<const HuffmanNode*, int> nodeIndices;
        std::list<const HuffmanNode*> first, second;
        for (int i = 0; i < n; ++i) {
            stream >> encoder.encodings[i].frequency;
            nodes.push_back({encoder.encodings[i].frequency, nullptr, nullptr});
            nodeIndices[&nodes.back()] = i;
            first.emplace_back(&nodes.back());
        }
        auto extract_min = [&first, &second]() -> const HuffmanNode* {
            if (second.empty() || (!first.empty() && (first.front()->frequency < second.front()->frequency))) {
                auto ret = first.front();
                first.pop_front();
                return ret;
            }
            auto ret = second.front();
            second.pop_front();
            return ret;
        };
        while ((first.size() + second.size()) > 1) {
            auto zero = extract_min();
            auto one  = extract_min();
            nodes.push_back({zero->frequency + one->frequency, zero, one});
            second.emplace_back(&nodes.back());
        }
        auto root = extract_min();
        traverse(0, 0, root, nodeIndices, encoder);
        encoder.totalLength = std::accumulate(encoder.encodings.begin(), encoder.encodings.end(), 0, [](uint64_t x, const Encoding& enc){
            return x + (enc.frequency * enc.length);
        });
        return encoder;
    }
};

int main()
{
    std::ifstream fin("huffman.in");
    HuffmanEncoder enc = HuffmanEncoder::fromStream(fin);
    std::ofstream fout("huffman.out");
    fout << enc.totalLength << "\n";
    for (const auto& encoding : enc.encodings) {
        fout << (int)encoding.length << " " << encoding.code << "\n";
    }
    return 0;
}