#include <fstream>
#include <iostream>
#include <queue>

using namespace std;

const int NMAX = 1000000;

long long sol[1 + NMAX];
int lung[1 + NMAX];

struct Nod
{
    long long frecv;
    bool frunza;
    int id;

    Nod* fiuSt;
    Nod* fiuDr;

    Nod() {};

    Nod(long long frecv, bool frunza, int id) :
        frecv(frecv), frunza(frunza), id(id) {};
};

queue<Nod*> q1;
queue<Nod*> q2;

Nod* nextNod()
{
    Nod* nod;

    if (q1.empty())
    {
        nod = q2.front();
        q2.pop();
        return nod;
    }
    else if (q2.empty())
    {
        nod = q1.front();
        q1.pop();
        return nod;
    }
    else
    {
        if (q1.front()->frecv <= q2.front()->frecv)
        {
            nod = q1.front();
            q1.pop();
            return nod;
        }
        else
        {
            nod = q2.front();
            q2.pop();
            return nod;
        }
    }
}

long long dfs(Nod* nod, int h, long long val)
{
    if (nod->frunza)
    {
        sol[nod->id]  = val;
        lung[nod->id] = h;
        return 0;
    }

    long long suma = 0;

    suma += dfs(nod->fiuSt, h + 1, val);

    suma += dfs(nod->fiuDr, h + 1, val |= (1ll << h));

    return suma + nod->frecv;
}

int main()
{
    ifstream in("huffmann.in");
    ofstream out("huffmann.out");

    int n;
    in >> n;

    for (int i = 1; i <= n; i++)
    {
        int v;
        in >> v;
        q1.push(new Nod(v, true, i));
    }

    while (q1.size() + q2.size() >= 2)
    {
        Nod* nod1 = nextNod();
        Nod* nod2 = nextNod();

        Nod* tata = new Nod(nod1->frecv + nod2->frecv, false, -1);
        q2.push(tata);

        tata->fiuSt = nod1;
        tata->fiuDr = nod2;
    }

    Nod* radacina = nextNod();

    out << dfs(radacina, 0, 0) << '\n';

    for (int i = 1; i <= n; i++)
        out << lung[i] << ' ' << sol[i] << '\n';

    return 0;
}