#include <fstream>
#include <queue>

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

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


long long unsigned a[1000001];
long long unsigned len[1000001];
long long unsigned code[1000001];

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)
{
    std::queue<Node*> internal;

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

        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)
    {
        len[node->pos] = length;
        code[node->pos] = val;
    }
}

int main()
{
    int n;
    f >> n;

    std::queue<Node*> initial;

    for(auto i = 0; i < n; ++i)
    {
        f >> a[i];

        Node *node = new Node;
        node->pos = i;
        node->val = a[i];
        node->left = nullptr;
        node->right = nullptr;

        initial.push(node);
    }

    Node* root;
    root = Huffman(initial);
    DepthFirst(root);

    long long unsigned lg = 0;
    for (auto i = 0; i < n; ++i)
    {
        lg += len[i] * a[i];
    }

    g << lg << '\n';

    for (auto i = 0; i < n; ++i)
    {
        g << len[i] << ' ' << code[i] << '\n';
    }

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

    return 0;
}