#include <fstream>

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

struct Node { long long val; int leftPos, rightPos;};

Node nodes[2000001];
long long unsigned len[1000001];
long long unsigned code[1000001];
long long unsigned lg = 0;

int getNodePosWithMinValue(Node nodes[], int& i, int& qFront, int qEnd, int n)
{
    int pos = -1;
    if(i >= n)
    {
        pos = qFront;
        ++qFront;
    }
    else if(qFront >= qEnd)
    {
        pos = i;
        ++i;
    }
    else
    {
        if(nodes[i].val < nodes[qFront].val)
        {
            pos = i;
            ++i;
        }
        else
        {
            pos = qFront;
            ++qFront;
        }
    }

    return pos;
}

int Huffman(Node nodes[], int n)
{
    int i=0;
    int qFront = n;
    int qEnd = n;

    while( ((n - i) + (qEnd - qFront)) > 1)
    {
        int leftPos = getNodePosWithMinValue(nodes, i, qFront, qEnd, n);
        int rightPos = getNodePosWithMinValue(nodes, i, qFront, qEnd, n);

        nodes[qEnd].val = nodes[leftPos].val + nodes[rightPos].val;
        nodes[qEnd].leftPos = leftPos;
        nodes[qEnd].rightPos = rightPos;
        lg += nodes[qEnd].val;
        ++qEnd;
    }

    return qFront;
}

void DepthFirst(Node nodes[], int pos, long long int val = 0, int length = 0)
{
    if (nodes[pos].leftPos != -1)
    {
        DepthFirst(nodes, nodes[pos].leftPos, val * 2, length + 1);
    }
    else
    {
        len[pos] = length;
        code[pos] = val;
    }

    if (nodes[pos].rightPos != -1)
    {
        DepthFirst(nodes, nodes[pos].rightPos, val * 2 + 1, length + 1);
    }
}

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

    for(auto i = 0; i < n; ++i)
    {
        f >> nodes[i].val;
        nodes[i].leftPos = -1;
        nodes[i].rightPos = -1;
    }

    int root = Huffman(nodes, n);

    DepthFirst(nodes, root);

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

    g << lg << '\n';

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

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

    return 0;
}