#include <queue>
#include <cstdlib>
#include <fstream>
#define Nmax 1000011
#define oo 100000000000000LL

/*
 *
 */
using namespace std;
typedef long long int lld;
typedef pair< lld, int > pr;
struct nod
{
    lld Cost;
    int left, right;
    nod( void ) : Cost(oo), left(0), right(0) {}
} t[2*Nmax];
queue< pr > Q, QQ;
lld Length[Nmax], Cod[Nmax];
inline void GetOutPut( int x, lld cod, lld length )
{
    if( t[x].left )
    {
        GetOutPut( t[x].left, cod<<1, length+1 );
        GetOutPut( t[x].right, (cod<<1)|1, length+1 );
    }
    else Length[x]=length, Cod[x]=x;
}
int main( void )
{
    lld s=0;
    pr x, y;
    int N, i, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>j;
        Q.push( pr( j, i ) );
    }
    for( s=0; false == Q.empty() || QQ.size() > 1; ++i )
    {
        if( false == Q.empty() )
        {
            if( false == QQ.empty() )
            {
                if( Q.front() <= QQ.front() )
                {
                    x=Q.front(); Q.pop();
                }
                else x=QQ.front(), QQ.pop();
                if( Q.empty() )
                    y=QQ.front(), QQ.pop();
                else if( QQ.empty() )
                        y=Q.front(), Q.pop();
                     else if( Q.front() <= QQ.front() )
                            y=Q.front(), Q.pop();
                          else y=QQ.front(), QQ.pop();
            }
            else {
                    x=Q.front(); Q.pop();
                    y=Q.front(); Q.pop();
                 }
        }
        else {
                x=QQ.front(); QQ.pop();
                y=QQ.front(); QQ.pop();
             }
        t[x.second].Cost=x.first; t[y.second].Cost=y.first;
        s+=( t[i].Cost=x.first+y.first );
        t[i].left=x.second, t[i].right=y.second;
        QQ.push( pr( t[i].Cost, i ) );
    }
    GetOutPut( i-1, 0, 0 );
    ofstream out( "huffman.out" );
    out<<s<<'\n';
    for( i=1; i <= N; ++i )
        out<<Length[i]<<' '<<Cod[i]<<'\n';
    return EXIT_SUCCESS;
}