#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <string>
#include <bitset>

using namespace std;

struct Node {
    long long freq;
    int symbol;
    Node* left;
    Node* right;

    Node(long long f, int s = -1, Node* l = nullptr, Node* r = nullptr)
        : freq(f), symbol(s), left(l), right(r) {}

    ~Node() {
        delete left;
        delete right;
    }
};

struct compare {
    bool operator()(Node* l, Node* r) {
        return l->freq > r->freq;
    }
};

void generateCodes(Node* root, string code, unordered_map<int, string>& huffmanCode) {
    if (!root) return;

    if (root->symbol != -1) {
        huffmanCode[root->symbol] = code;
    }

    generateCodes(root->left, code + "0", huffmanCode);
    generateCodes(root->right, code + "1", huffmanCode);
}

int main() {
    ifstream infile("huffman.in");
    ofstream outfile("huffman.out");

    if (!infile || !outfile) {
        cerr << "Error opening file" << endl;
        return 1;
    }

    int n;
    infile >> n;

    vector<long long> freqs(n);
    for (int i = 0; i < n; ++i) {
        infile >> freqs[i];
    }

    priority_queue<Node*, vector<Node*>, compare> pq;

    for (int i = 0; i < n; ++i) {
        pq.push(new Node(freqs[i], i));
    }

    while (pq.size() > 1) {
        Node* left = pq.top(); pq.pop();
        Node* right = pq.top(); pq.pop();

        long long sum = left->freq + right->freq;
        pq.push(new Node(sum, -1, left, right));
    }

    Node* root = pq.top();

    unordered_map<int, string> huffmanCode;
    generateCodes(root, "", huffmanCode);

    long long totalLength = 0;
    vector<pair<int, long long>> codes;
    for (int i = 0; i < n; ++i) {
        string code = huffmanCode[i];
        totalLength += freqs[i] * code.length();
        long long binaryCode = stoll(code, nullptr, 2);
        codes.emplace_back(code.length(), binaryCode);
    }

    outfile << totalLength << endl;
    for (const auto& p : codes) {
        outfile << p.first << " " << p.second << endl;
    }

    delete root;  // Free the memory allocated for the Huffman tree

    infile.close();
    outfile.close();

    return 0;
}