#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 1000011
#define llu unsigned long long int

using namespace std;
struct vertex
{
	llu frecv;
	int index;
	vertex *left, *right;
	vertex() : frecv(-1), index(-1), left(NULL), right(NULL) {  }
	vertex( llu _frecv, int _index, vertex* _left=NULL, vertex* _right=NULL ) : frecv(_frecv), index(_index), left(_left), right(_right) {}
} *v[2];
queue< vertex* > Q, QQ;
llu Length[N_MAX], Code[N_MAX];
inline void GetBinaryCode( vertex* x, llu c, llu l )
{
	if( x->left )
	{
		GetBinaryCode( x->left, 2*c, l+1 );
		GetBinaryCode( x->right, 2*c+1, l+1 );
	}
	else Length[x->index]=l, Code[x->index]=c;
}
int main( void )
{
	llu s=0;
	int N, i, x, j;
	ifstream in( "huffman.in" );
	in>>N;
	for( i=1; i <= N; ++i )
	{
		in>>x;
		Q.push( new vertex( x, i ) );		
	}
	j=N;
	while( Q.size()+QQ.size() >= 2 )
	{
		for( i=0; i < 2 && !Q.empty() && !QQ.empty(); ++i )
			if( Q.front()->frecv <= QQ.front()->frecv )
				v[i]=Q.front(), Q.pop();
			else v[i]=QQ.front(), QQ.pop();
		if( i < 2 && !Q.empty() )
			for( ; i < 2; ++i )
				v[i]=Q.front(), Q.pop();
		if( i < 2 && !QQ.empty() )
			for( ; i < 2; ++i )
				v[i]=QQ.front(), QQ.pop();
		s+=v[0]->frecv+v[1]->frecv;
		QQ.push( new vertex( v[0]->frecv+v[1]->frecv, -1, v[0], v[1] ) );
	}
	GetBinaryCode( QQ.front(), 0, 0 );
	ofstream out( "huffman.out" );
	out<<s<<'\n';
	for( x=1; x <= N; ++x )
		out<<Length[x]<<' '<<Code[x]<<'\n';
	return EXIT_SUCCESS;
}