#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 &k)
{
	c[0]->info=1;
	c[k++]=r;
}

int emptyQueue(nod **c)
{
	if(c[0]->info==-1)
		return 1;
	return 0;
}

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

nod* creareHuffman(long n,nod **c1)
{
	nod **c2=(nod**)malloc((n+1)*sizeof(nod*));
	nod *x,*y,*r;
	for(long i=0;i<=n;i++)
		c2[i]=(nod*)malloc(sizeof(nod));
	c2[0]->info=-1;
	long i,j=1,k=1,poz=1;
	for(i=1;i<=n-1;i++)
	{
		x=extrageMin(c1,c2,j,k);
		if(j>n)
			c1[0]->info=-1;
		y=extrageMin(c1,c2,j,k);
		if(j>n)
			c1[0]->info=-1;
		r=(nod*)malloc(sizeof(nod));
		r->info=x->info+y->info;
		r->st=x;
		r->dr=y;
		addQueue(r,c2,poz);
	}
	r=c2[k];
	return r;
}

long long lungime(nod *r)
{
	if(r)
	{
		if(r->st!=r->dr)
			return r->info+lungime(r->st)+lungime(r->dr);
		else
			return 0;
	}
}

void coduri(nod *r,char *s,long i,FILE *g)
{
	if(r)
	{
		if(r->st!=r->dr)
		{
			s[i]='0';
			coduri(r->st,s,++i,g);
			--i;
			s[i]='1';
			coduri(r->dr,s,++i,g);
			--i;
		}
		else
		{
		    s[i]='\0';
			long a=strlen(s);
			fprintf(g,"%ld ",a);
			long long b=0;
			for(long j=a-1;j>=0;j--)
			{
				b+=(int)(s[j]-'0')<<(a-j-1);
			}
			fprintf(g,"%lld\n",b);
			--i;
		}
	}
}

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=lungime(r);
	fprintf(g,"%lld\n",lg);
	char *s=(char*)malloc(1000000);
	long i=0;
	coduri(r,s,i,g);
	fclose(g);
	fclose(f);
	return 0;
}