#include <fstream>
#include <queue>

std::ifstream f("huffman.in");
std::ofstream g("huffman.out");

struct Node { long long pos, val; Node *next, *left, *right; };

Node* createNode(long long val, Node* left, Node* right)
{
    Node *node = new Node;
    node->val = val;
    node->left = left;
    node->right = right;

    return node;
}

Node* getNodeWithMinValue(std::queue<Node*>& initial, std::queue<Node*>& internal)
{
    Node* node = nullptr;
    if(initial.empty())
    {
        node = internal.front();
        internal.pop();
    }
    else if(internal.empty())
    {
        node = initial.front();
        initial.pop();
    }
    else
    {
        Node* initialFront = initial.front();
        Node* internalFront = internal.front();
        if(initialFront->val < internalFront->val)
        {
            node = initialFront;
            initial.pop();
        }
        else
        {
            node = internalFront;
            internal.pop();
        }
    }
    return node;
}

Node* Huffman(std::queue<Node*> initial, unsigned long long &lg)
{
    std::queue<Node*> internal;

    lg = 0;
    while( ( initial.size() + internal.size() ) > 1)
    {
        Node* left = getNodeWithMinValue(initial, internal);
        Node* right = getNodeWithMinValue(initial, internal);

        lg += left->val + right->val;
        internal.push(createNode(left->val + right->val, left, right));
    }

    return internal.front();
}

void DepthFirst(Node* node, long long int val = 0, int length = 0)
{
    if (node->left != nullptr)
    {
        DepthFirst(node->left, val * 2, length + 1);
    }

    if (node->right != nullptr)
    {
        DepthFirst(node->right, val * 2 + 1, length + 1);
    }

    if (node->right == nullptr && node->left == nullptr)
    {
        g<< length << ' ' << val << '\n';
    }
}

int main()
{
    long long int n = 0, x = 0;
    f >> n;

    std::queue<Node*> initial;

    for(auto i = 0LL; i < n; ++i)
    {
        f >> x;

        Node *node = new Node;
        node->pos = i;
        node->val = x;
        node->left = nullptr;
        node->right = nullptr;

        initial.push(node);
    }

    unsigned long long lg = 0;
    Node* root;
    root = Huffman(initial, lg);

    g << lg << '\n';
    DepthFirst(root);

    f.close();
    g.close();

    return 0;
}