#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;
	int left, right;
	vertex() : frecv(-1), index(-1), left(NULL), right(NULL) {  }
	vertex( llu _frecv, int _index, int _left=NULL, int _right=NULL ) : frecv(_frecv), index(_index), left(_left), right(_right) {}
} v[2], T[2*N_MAX];
llu s;
queue< int > Q, QQ;
llu Length[N_MAX], Code[N_MAX];
inline void GetBinaryCode( vertex x, llu c, llu l )
{
	if( x.left )
	{
		GetBinaryCode( T[x.left], 2*c, l+1 );
		GetBinaryCode( T[x.right], 2*c+1, l+1 );
	}
	else Length[x.index]=l, Code[x.index]=c;
}
int main( void )
{
	int N, i, x, j;
	ifstream in( "huffman.in" );
	in>>N;
	for( i=1; i <= N; ++i )
	{
		in>>x;
		T[i].frecv=x;
		T[i].index=i;
		Q.push( i );		
	}
	j=N;
	while( Q.size()+QQ.size() >= 2 )
	{
		for( i=0; i < 2 && !Q.empty() && !QQ.empty(); ++i )
			if( T[Q.front()].frecv <= T[QQ.front()].frecv )
				v[i]=T[Q.front()], Q.pop();
			else v[i]=T[QQ.front()], QQ.pop();
		if( i < 2 && !Q.empty() )
			for( ; i < 2; ++i )
				v[i]=T[Q.front()], Q.pop();
		if( i < 2 && !QQ.empty() )
			for( ; i < 2; ++i )
				v[i]=T[QQ.front()], QQ.pop();
		s+=v[0].frecv+v[1].frecv;
		++j;
		T[j].frecv=v[0].frecv+v[1].frecv;
		T[j].left=v[0].index; T[j].right=v[1].index;
		T[j].index=j;
		QQ.push( j );
	}
	GetBinaryCode( T[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;
}