#include <stdio.h>
#define maxt 2100000
#define maxn 1050000

struct Tree { long long v; int sym; int s[2]; } T[maxt];

int N, root, Q[2][maxn], L[maxn];
long long lg, B[maxn];

void read () ;
void buildTree () ;
void DF (int i, int level, long long path) ;

int main ()
{
    FILE *out; int i;

    read () ;
    buildTree () ;
    DF (root, 0, 0LL);

    out = fopen("huffman.out", "w");

    fprintf (out, "%lld\n", lg);
    for(i = 0; i < N; ++i)
        fprintf (out, "%d %lld\n", L[i], B[i]);

    fclose(out);
    return 0;
}

void DF (int i, int level, long long path)
{
    if ( T[i].s[0] != -1)
        DF ( T[i].s[0], level + 1, path<<1 );
    if ( T[i].s[1] != -1)
        DF ( T[i].s[1], level + 1, (path<<1) + 1 );

    if (T[i].s[0] == -1 && T[i].s[0] == -1)
    {
        L[ T[i].sym ] = level;
        B[ T[i].sym ] = path;
        lg += T[i].v * level;
    }
}

void buildTree ()
{
    int l[2], r[2], v[2][2], vi, i, k;

    k = -1;
    l[0] = 0; r[0] = N-1;
    l[1] = 0; r[1] = -1;

    while ( l[0] <= r[0] || l[1] < r[1] )
    {
        vi = -1;

        if (l[0] <= r[0])
            ++vi, v[0][vi] = l[0], v[1][vi] = 0;
        if (l[0]+1 <= r[0])
            ++vi, v[0][vi] = l[0]+1, v[1][vi] = 0;

        if ( l[1] <= r[1] )
        {
            for (i = 0; i <= vi && (T[ Q[1][ l[1] ] ].v >= Q[0][ v[0][i] ]); ++i) ;

            if (i < 2)
            {
                if (i == 0 && vi >= 0)
                    v[0][1] = v[0][0], v[1][1] = 0, vi = 1;
                if (vi == -1)
                    vi = 0;

                v[0][i] = l[1];
                v[1][i] = 1;
            }

            if (i == 0 && l[1]+1 <= r[1] && ( vi == 0 || T[ Q[1][ l[1]+1 ] ].v < Q[0][ v[0][1] ]) )
                    v[0][1] = l[1]+1, v[1][1] = 1, vi = 1;
        }

        l[ v[1][0] ]++; l[ v[1][1] ]++;

        if ( v[1][0] == 0)
            ++k, T[k].v = Q[0][ v[0][0] ], T[k].s[0] = T[k].s[1] = -1, T[k].sym = v[0][0], v[0][0] = k;
        else
            v[0][0] = Q[1][ v[0][0] ];

        if ( v[1][1] == 0)
            ++k, T[k].v = Q[0][ v[0][1] ], T[k].s[0] = T[k].s[1] = -1, T[k].sym = v[0][1], v[0][1] = k;
        else
            v[0][1] = Q[1][ v[0][1] ];

        T[++k].v =T[ v[0][0] ].v + T[ v[0][1] ].v;
        T[k].s[0] = v[0][0]; T[k].s[1] = v[0][1];

        Q[1][ ++r[1] ] = k;
    }
    root = Q[1][ l[1] ];
}

void read ()
{
    FILE *in = fopen ("huffman.in", "r");
    int i;

    fscanf (in, "%d", &N);
    for (i = 0; i < N; ++i)
        fscanf (in, "%d", &Q[0][i]);

    fclose (in);
}