#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<( tree y )
	{
		return Cost < y.Cost;
	}
	bool operator<=( tree y )
	{
		return Cost <= y.Cost;
	}
    void GetOutput( lld cod, lld length )
    {
        if( this->left )
        {
            this->left->GetOutput( cod<<1, length+1 );
            this->right->GetOutput( (cod<<1)|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( Q.size() + QQ.size() > 1 )
    {
        if( Q.size() > 0 )
        {
            if( QQ.size() > 1 )
            {
                if( *Q.front() <= *QQ.front() )
                {
                    x=Q.front(); Q.pop();
                }
                else x=QQ.front(), QQ.pop();
                if( false == Q.empty()  && *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();
             }
        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;
}