#include <fstream>
#include <cstdint>
#include <list>
#include <vector>
#include <queue>
#include <functional>
struct Huffman {
    struct Encoding {
        uint64_t val;
        uint64_t len;
    };
    using FrequencyType = uint64_t;
    using ElementType = uint64_t;
    using EncodingType = Encoding;
    struct Node {
        
        enum class Type {
            Regular,
            Leaf
        };
        Node* left = nullptr;
        Node* right = nullptr;
        ElementType element = 0;
        Type type;
        FrequencyType freq;
        int height = 0;
        Node(FrequencyType freq)
        : freq(freq)
        , type(Type::Regular) {}
        Node(FrequencyType freq, ElementType element)
        : freq(freq)
        , element(element)
        , type(Type::Leaf) {}
    };
private:

    int characters;
    std::vector<EncodingType> encodings;
    int totalLength;

    Huffman(int characters) : characters(characters) {
        encodings.reserve(characters);
    }
    static uint64_t Follow(Huffman& h, Node* node, uint64_t currMask, uint64_t height) {
        if (node->type == Node::Type::Leaf) {
            h.encodings[node->element] = Encoding{currMask, height};
            node->height = height;
            return height * node->freq;
        } else {
            const auto h1 = Follow(h, node->left, currMask << 1, height + 1);
            const auto h2 = Follow(h, node->right, (currMask << 1) | 1, height + 1);
            return h1 + h2;
        }
    }
public:
    int NumCharacters() const { return characters; }
    int TotalLength() const { return totalLength; }
    EncodingType EncodingFor(ElementType el) const { return encodings[el]; }
    static Huffman Construct(std::ifstream& f) {
        std::list<Node> nodes;
        Node* root = nullptr;
        int readNodes = 0;
        int numNodes;
        f >> numNodes;
        struct Comp {
            bool operator()(const Node* lhs, const Node* rhs) const {
                return lhs->freq >= rhs->freq;
            }
        };
        std::priority_queue<Node*, std::vector<Node*>, Comp> q;
        Huffman h{numNodes};
        for (uint64_t i = 0u; i < numNodes; ++i) {
            FrequencyType freq;
            f >> freq;
            nodes.emplace_back(freq, ElementType{i});
            q.push(&nodes.back());
        }
        while (true) {
            Node* left = q.top();
            q.pop();
            if (q.empty()) {
                root = left;
                break;
            }
            Node* right = q.top();
            q.pop();
            const auto sumfreq = left->freq + right->freq;
            nodes.emplace_back(sumfreq);
            Node* newNode = &nodes.back();
            newNode->left = left;
            newNode->right = right;
            q.push(newNode);
        }
        h.totalLength = Follow(h, root, 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 (int i = 0; i < h.NumCharacters(); ++i) {
        const auto encoding = h.EncodingFor(i);
        fout << encoding.len << ' ' << encoding.val << '\n';
    }
    return 0;
}