#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 1000000;

short int lung[NMAX];
unsigned long long sol[NMAX];

struct Nod
{
    long long frecv;
    int id;

    int fiuSt = -1;
    int fiuDr = -1;

    Nod() = default;

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

vector<Nod> noduri;

queue<int> q1;
queue<int> q2;

int nextNod()
{
    int poz;

    if (q1.empty())
    {
        poz = q2.front();
        q2.pop();
        return poz;
    }
    else if (q2.empty())
    {
        poz = q1.front();
        q1.pop();
        return poz;
    }
    else
    {
        if (noduri[q1.front()].frecv <= noduri[q2.front()].frecv)
        {
            poz = q1.front();
            q1.pop();
            return poz;
        }
        else
        {
            poz = q2.front();
            q2.pop();
            return poz;
        }
    }
}

long long dfs(int poz, short int h, unsigned long long val)
{
    if (noduri[poz].id != -1)
    {
        lung[noduri[poz].id] = h;
        sol[noduri[poz].id]  = val;
        return 0;
    }

    long long suma = 0;

    suma += dfs(noduri[poz].fiuSt, h + 1, val);
    suma += dfs(noduri[poz].fiuDr, h + 1, val |= ((1ull) << h));

    return suma + noduri[poz].frecv;
}

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

    int n;
    in >> n;

    if (n == 1)
    {
        int v;
        in >> v;

        out << v << '\n';
        out << 1 << ' ' << 0 << '\n';

        return 0;
    }

    for (int i = 0; i < n; i++)
    {
        int v;
        in >> v;

        noduri.emplace_back(v, i);
        q1.push(noduri.size() - 1);
    }

    while (q1.size() + q2.size() >= 2)
    {
        int poz1 = nextNod();
        int poz2 = nextNod();

        noduri.emplace_back(noduri[poz1].frecv + noduri[poz2].frecv, -1);
        noduri.back().fiuSt = poz1;
        noduri.back().fiuDr = poz2;

        q2.push(noduri.size() - 1);
    }

    int radacina = nextNod();

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < lung[i] / 2; j++)
        {
            if (((((1ull) << j) & sol[i]) == (0ull)) && (((1ull) << (lung[i] - 1 - j)) & sol[i]))
            {
                sol[i] |= ((1ull) << j);
                sol[i] -= ((1ull) << (lung[i] - 1 - j));
            }
            else if ((((1ull) << j) & sol[i]) && ((((1ull) << (lung[i] - 1 - j)) & sol[i]) == 0ull))
            {
                sol[i] -= ((1ull) << j);
                sol[i] |= ((1ull) << (lung[i] - 1 - j));
            }
        }

        out << lung[i] << ' ' << sol[i] << '\n';
    }

    return 0;
}