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

struct HuffmanEncoder {
    struct Encoding {
        using EncodingSizeType = uint64_t;
        using EncodingValueType = uint64_t;
        EncodingSizeType size = 0;
        EncodingValueType value = 0;
        EncodingSizeType originalPriority = 0;
    };
    struct HuffmanNode {
        using PriorityValueType = uint64_t;
        PriorityValueType priority;
        std::list<std::vector<Encoding>::iterator> leaves;
    };

    struct NodeComp {
        bool operator()(const HuffmanNode& lhs, const HuffmanNode& rhs) const {
            return lhs.priority > rhs.priority;
        }
    };
    std::vector<Encoding> encodings;
    Encoding::EncodingSizeType totalLength = 0;
    HuffmanEncoder(uint32_t numSymbols) : encodings(numSymbols) {

    }
    template<typename T>
    static HuffmanEncoder fromStream(T& stream) {
        int n;
       stream >> n;
        HuffmanEncoder encoder(n);
        std::vector<HuffmanNode> heap;
        heap.reserve(n);
        for (int i = 0; i < n; ++i) {
            HuffmanNode::PriorityValueType priority;
            stream >> priority;
            heap.push_back({priority, {encoder.encodings.begin() + i}});
            encoder.encodings[i].originalPriority = priority;
        }
        NodeComp nc;
        auto pop_heap = [&heap, &nc] () {
            std::pop_heap(heap.begin(), heap.end(), nc);
            auto foo = std::move(heap.back());
            heap.pop_back();
            return foo;
        };
        while (heap.size() > 1) {
            auto left = pop_heap();
            auto right = pop_heap();

            for (auto nodeIt: left.leaves) {
                auto& node = *nodeIt;
                ++node.size;
            }
            for (auto nodeIt: right.leaves) {
                auto& node = *nodeIt;
                node.value |= 1 << node.size;
                ++node.size;
            }
            auto concattedList = std::move(left.leaves);
            concattedList.splice(concattedList.begin(), std::move(right.leaves));
            auto newNode = HuffmanNode{left.priority + right.priority, std::move(concattedList)};
            heap.emplace_back(std::move(newNode));
            std::push_heap(heap.begin(), heap.end(), nc);
        }
        auto node = std::move(heap.front());
        encoder.totalLength = std::accumulate(encoder.encodings.begin(), encoder.encodings.end(), 0, [](Encoding::EncodingSizeType t, const Encoding& e){
            return t + e.originalPriority * e.size;
        });
        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 << encoding.size << " " << encoding.value << "\n";
    }
    return 0;
}