#include <queue>
#include <vector>
#include <fstream>
#include <cstdlib>
#define N_MAX 1000011

using namespace std;
struct vertex
{
	long long int frecv;
	int value;
	vertex *left, *right;
	vertex() : frecv(0), value(0), left(NULL), right(NULL) {}
	vertex( long long int _frecv, char _value ) : frecv(_frecv), value(_value), left(NULL), right(NULL) {}
	vertex( long long int _frecv, char _value, vertex *_left, vertex *_right ) : frecv(_frecv), value(_value), left(_left), right(_right) {}
	bool operator<( const vertex& x ) const { return frecv < x.frecv; }
} *root;
long long int s=0;
long long int Length[N_MAX], Code[N_MAX];
queue< vertex* > Q, QQ;
inline vertex* Add( vertex *x, vertex *y )
{
	vertex *z=new vertex( x->frecv+y->frecv, 0, x, y );
	return z;
}
inline void GetBinaryCode( vertex* x, long long int v, long long int l )
{
	if( x->left )
	{
		GetBinaryCode( x->left, 2*v, l+1 );
		GetBinaryCode( x->right, 2*v+1, l+1 );
	}
	else Length[x->value]=l, Code[x->value]=v;
}
int main( void )
{
	int N, i, x;
	ifstream in( "huffman.in" );
	in>>N;
	for( i=1; i <= N; ++i )
	{
		in>>x;
		Q.push( new vertex( x, i ) );
	}
	while( Q.size()+QQ.size() >= 2 )
	{
		vertex *v[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();
		QQ.push( Add( v[0], v[1] ) );
		s+=QQ.back()->frecv;
	}
	root=QQ.front(); QQ.pop();
	GetBinaryCode( root, 0, 0 );
	ofstream out( "huffman.out" );
	out<<s<<'\n';
	for( i=1; i <= N; ++i )
		out<<Length[i]<<' '<<Code[i]<<'\n';
	return EXIT_SUCCESS;
}