#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 1000011
#define llu unsigned long long int

using namespace std;
struct vertex
{
    llu frecv;
    int index;
    int left, right;
    vertex() : frecv(-1), index(-1), left(NULL), right(NULL) {  }
    vertex( llu _frecv, int _index, int _left=NULL, int _right=NULL ) : frecv(_frecv), index(_index), left(_left), right(_right) {}
} v[2], T[2*N_MAX];
llu s;
queue< int > Q, QQ;
llu Length[N_MAX], Code[N_MAX];
inline void GetBinaryCode( vertex x, llu c, llu l )
{
    if( x.left )
    {
        GetBinaryCode( T[x.left], 2*c, l+1 );
        GetBinaryCode( T[x.right], 2*c+1, l+1 );
    }
    else Length[x.index]=l, Code[x.index]=c;
}
int main( void )
{
    int N, i, x, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>x;
        T[i].frecv=x;
        T[i].index=i;
        Q.push( i );
    }
    j=N;
    while( Q.size()+QQ.size() >= 2 )
    {
        for( i=0; i < 2 && !Q.empty() && !QQ.empty(); ++i )
            if( T[Q.front()].frecv <= T[QQ.front()].frecv )
                v[i]=T[Q.front()], Q.pop();
            else v[i]=T[QQ.front()], QQ.pop();
        if( i < 2 && !Q.empty() )
            for( ; i < 2; ++i )
                v[i]=T[Q.front()], Q.pop();
        if( i < 2 && !QQ.empty() )
            for( ; i < 2; ++i )
                v[i]=T[QQ.front()], QQ.pop();
        s+=v[0].frecv+v[1].frecv;
        ++j;
        T[j].frecv=v[0].frecv+v[1].frecv;
        T[j].left=v[0].index; T[j].right=v[1].index;
        T[j].index=j;
        QQ.push( j );
    }
    GetBinaryCode( T[QQ.front()], 0, 0 );
    ofstream out( "huffman.out" );
    out<<s<<'\n';
    for( x=1; x <= N; ++x )
        out<<Length[x]<<' '<<Code[x]<<'\n';
    return EXIT_SUCCESS;
}