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

/*
 *
 */
using namespace std;
typedef long long int lld;
lld Length[Nmax], Cod[Nmax];
class tree
{
    int idx;
    lld Cost;
    tree *left, *right;
public:
    tree( int _idx=0, lld _Cost=oo, tree* _left=NULL, tree* _right=NULL ) : idx(_idx), Cost(_Cost), left(_left), right(_right) {}
    lld& Add( tree* &x, tree* &y, int _idx=0 )
    {
        idx=_idx;
        Cost=x->Cost+y->Cost;
        left=x; right=y;
        return Cost;
    }
	bool operator<( const tree* y ) const 
	{
		return Cost < y->Cost;
	}
    void GetOutput( lld cod, lld length )
    {
        if( this->left )
        {
            this->left->GetOutput( 2*cod, length+1 );
            this->right->GetOutput( 2*cod+1, length+1 );
        }
        Length[this->idx]=length;
        Cod[this->idx]=cod;
    }
} *x, *y;
queue< tree* > Q, QQ;
int main( void )
{
    lld s=0, c;
    int N, i, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>j;
        Q.push( new tree( i, j ) );
    }
    while( false == Q.empty() || QQ.size() > 1 )
	{
		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();
					if( Q.empty() )
						y=QQ.front(), QQ.pop();
					else y=Q.front(), Q.pop();
				 }
		}
		else {
				x=QQ.front(); QQ.pop();
				y=QQ.front(); QQ.pop();
			 }
		tree* z=new tree;
		c=z->Add( x, y );
		s+=c;
		QQ.push(z);
	}
	QQ.front()->GetOutput( 0, 0 );
	ofstream out( "huffman.out" );
	out<<s<<'\n';
	for( i=1; i <= N; ++i )
		out<<Length[i]<<' '<<Cod[i]<<'\n';	
	return EXIT_SUCCESS;
}