#include <map>
#include <cstdlib>
#include <fstream>
#define Nmax 2000011
#define oo 10000000000000000LL

/*
 *
 */
using namespace std;
typedef long long int lld;
typedef pair< lld, int > pr;
struct tree
{
    lld Cost;
    int left, right;
    tree( void ) : Cost(oo), left(0), right(0) {}
    tree( lld _Cost, int _left, int _right ) : Cost(_Cost), left(_left), right(_right) {}
} t[Nmax];
lld length[Nmax], Cod[Nmax];
multimap< lld, int > v;
inline void OutPut( int x, lld cod, lld idx )
{
    if( t[x].left )
    {
         OutPut( t[x].left, 2*cod, idx+1 );
         OutPut( t[x].right, 2*cod+1, idx+1 );
         return;
    }
    Cod[x]=cod;
    length[x]=idx;
}
int main( void )
{
    lld s;
    pr x, y;
    int N, i, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>j;
        v.insert( pr( j, i ) );
    }
    for( s=0; v.size() > 1; ++i )
    {
        x=*(v.begin());
        v.erase( v.begin() );
        y=*(v.begin());
        v.erase( v.begin() );
        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;
        v.insert( pr( t[i].Cost, i ) );
    }
    ofstream out( "huffman.out" );
    out<<s<<'\n';
    OutPut( i-1, 0, 0 );
    for( i=1; i <= N; ++i )
        out<<length[i]<<' '<<Cod[i]<<'\n';
    return EXIT_SUCCESS;
}