#include<fstream>
#include<map>
#include<vector>
using namespace std;

struct Nod
{
	long long fr;
	int c;
	struct Nod *st,*dr;
};
typedef struct Nod *Arbore;
Arbore R;

int n;
int M[1000002];
long long Cod[1000002];
short nr[1000002];
vector <Arbore> H;

inline bool SortareHeap(Arbore A,Arbore B)
{
	if(A->fr==B->fr)
		return A->c>B->c;
	return A->fr>B->fr;
}

inline void Citire()
{
	int i,x;
	ifstream fin("huffman.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>x;
		M[i]=x;
		Arbore aux=new Nod;
		aux->c=i;
		aux->fr=x;
		aux->st=aux->dr=NULL;
		H.push_back(aux);
	}
	fin.close();
	make_heap(H.begin(),H.end(),SortareHeap);
}

inline void Construire_Arbore_Huffman()
{
	int i;
	Arbore X,Y;
	for(i=1;i<n;i++)
	{
		//extrag succesiv doua elemente din min-heap
		X=H.front();
		pop_heap(H.begin(),H.end(),SortareHeap);
		H.pop_back();
		
		Y=H.front();
		pop_heap(H.begin(),H.end(),SortareHeap);
		H.pop_back();
		
		//unific arborii X si Y creand noul nod radacina Z
		Arbore Z=new Nod;
		Z->st=X;
		Z->dr=Y;
		Z->fr=X->fr+Y->fr;
		Z->c=0;
		
		//si il introduc in min-heap
		H.push_back(Z);
		push_heap(H.begin(),H.end(),SortareHeap);
	}
	//singurul nod ramas in min-heap este radacina arborelui Huffman
	R=H.front();
}

inline void Generare_Coduri_Huffman(Arbore r,long long cod,short lg)
{
	if(r->st)
		Generare_Coduri_Huffman(r->st,(cod<<1),lg+1);
	if(r->dr)
		Generare_Coduri_Huffman(r->dr,(cod<<1)+1,lg+1);
	if(r->c) //am ajuns la un nod terminal,deci am ajuns la un caracter si am codul lui
	{
		Cod[r->c]=cod;
		nr[r->c]=lg;
	}
}

void Afisare()
{
	ofstream fout("huffman.out");
	int i;
	long long lg=0;
	for(i=1;i<=n;i++)
		lg=lg+M[i]*nr[i];
	fout<<lg<<"\n";
	for(i=1;i<=n;i++)
		fout<<nr[i]<<' '<<Cod[i]<<"\n";
	fout.close();
}

int main()
{
	Citire();
	Construire_Arbore_Huffman();
	Generare_Coduri_Huffman(R,0,0);
	Afisare();
	return 0;
}