#include <map>
#include <cstdlib>
#include <fstream>
#define Nmax 2000011
#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( void ) : idx(0), Cost(oo), left(NULL), right(NULL) {}
    tree( int _idx, lld _Cost, tree* _left, tree* _right ) : idx(_idx), Cost(_Cost), left(_left), right(_right) {}
    lld Add( int _idx, tree* &x, tree* &y )
    {
        idx=_idx;
        Cost=x->Cost+y->Cost;
        left=x; right=y;
        return Cost;
    }
    bool operator<( const tree* &z ) const
    {
        return Cost < z->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 );
        }
        Cod[this->idx]=cod;
        Length[this->idx]=length;
    }
};
typedef pair< lld, tree* > pr;
multimap< lld, tree* > v;
int main( void )
{
    pr x, y;
    lld s, c;
    int N, i, j;
    ifstream in( "huffman.in" );
    in>>N;
    for( i=1; i <= N; ++i )
    {
        in>>j;
        v.insert( pr( j,  new tree( i, j, NULL, NULL ) )  );
    }
    for( s=0; v.size() > 1; ++i )
    {
        x=*(v.begin());
        v.erase( v.begin() );
        y=*(v.begin());
        v.erase(v.begin());
        tree* z=new tree;
        c=z->Add( i, x.second, y.second );
        s+=c;
		v.insert( pr( c, z ) );
    }
    x=*(v.begin());
    x.second->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;
}