#include <cstdio>
#include <cstdlib>
#include <cstring>
struct nod
{
	long long info;
	nod *st,*dr;
};
void citire(FILE *f,long &n,nod **&c1)
{
	fscanf(f,"%ld",&n);
	c1=(nod**)malloc((n+1)*sizeof(nod**));
	c1[0]=(nod*)malloc(sizeof(nod));
	for(long i=1;i<=n;i++)
	{
		c1[i]=(nod*)malloc(sizeof(nod));
		fscanf(f,"%lld",&c1[i]->info);
		c1[i]->st=c1[i]->dr=NULL;
	}
}

void addQueue(nod *r,nod **&c,long &st,long &dr)
{
	dr++;
	c[dr]=(nod*)malloc(sizeof(nod));
	c[dr]=r;
}

int emptyQueue(nod **c,long st,long dr)
{
	if(dr<st)
		return 1;
	return 0;
}

nod* extrageMin(nod **&c1,nod **&c2,long &st1,long &dr1,long &st2, long &dr2)
{
	nod *min;
	if(emptyQueue(c2,st2,dr2))
		min=c1[st1++];
	else
		if(emptyQueue(c1,st1,dr1))
			min=c2[st2++];
		else
			if(c1[st1]->info<=c2[st2]->info)
				min=c1[st1++];
			else
				min=c2[st2++];
	return min;
}

nod* creareHuffman(long n,nod **c1,long long &lg)
{
	lg=0;
	nod **c2=(nod**)malloc((n+1)*sizeof(nod*));
	nod *x,*y,*r;
	long st1=1,dr1=n,st2=1,dr2=0,i;
	for(i=1;i<=n-1;i++)
	{
		x=extrageMin(c1,c2,st1,dr1,st2,dr2);
		y=extrageMin(c1,c2,st1,dr1,st2,dr2);
		r=(nod*)malloc(sizeof(nod));
		r->info=x->info+y->info;
		r->st=x;
		r->dr=y;
		lg+=r->info;
		addQueue(r,c2,st2,dr2);
	}
	r=c2[st2];
	return r;
}

void coduri(nod *r,long long cod,long nivel,FILE *g)
{
	if(r->st)
	{
		coduri(r->st,cod*2,nivel+1,g);
		coduri(r->dr,cod*2+1,nivel+1,g);
		return;
	}
	fprintf(g,"%ld %lld\n",nivel,cod);
}

int main()
{
	FILE *f=fopen("huffman.in","r");
	FILE *g=fopen("huffman.out","w");
	nod **c1,*r;
	long n;
	long long lg;
	citire(f,n,c1);
	r=creareHuffman(n,c1,lg);
	fprintf(g,"%lld\n",lg);
	coduri(r,0,0,g);
	fclose(g);
	fclose(f);
	return 0;
}