#include <stdio.h>
#include <stdlib.h>

typedef struct _nod
{
	int val;
	long long b;
	int lg;
	struct _nod * f[2];
} nod;


nod * hp[1000000];

int nhp;

void hp_swap(int a, int b)
{
	nod * aux = hp[a];
	hp[a]=hp[b];
	hp[b]=aux;
}

void hp_up(int i)
{
	while (i)
	{
		int pos = ((i+1)>>1)-1;
		if (hp[i]->val>=hp[pos]->val)
			break;
		hp_swap(i,pos);
		i=pos;
	}
}

void hp_down(int i)
{
	while (1)
	{
		int p1=(i<<1)+1;
		int p2=(i<<1)+2;
		int min=i;
		if ((p1<nhp)&&(hp[p1]->val<hp[min]->val))
			min=p1;
		if ((p2<nhp)&&(hp[p2]->val<hp[min]->val))
			min=p2;
		if (min==i)
			break;
		hp_swap(min,i);
		i=min;
	}
}

nod * hp_popmin()
{
	nod * res = hp[0];
	hp_swap(0,--nhp);
	hp_down(0);
	return res;
}

void hp_push(nod * val)
{
	hp[nhp++]=val;
	hp_up(nhp-1);
}


FILE *fin;
FILE *fout;

nod a[1000000];
nod t[1000000];
int nt=0;
long long sum=0;

void dfs(nod * nd)
{
	int i;
	for (i=0; i<=1; i++)
	{
		if (nd->f[i]==NULL) continue;
		nd->f[i]->b=(((nd->b)<<1)|i);
		nd->f[i]->lg=nd->lg+1;
		dfs(nd->f[i]);
	}
	if (!(nd->f[0])&&!(nd->f[1]))
		sum+=(nd->lg)*(long long)(nd->val);
}

int main (int argc, char * const argv[]) {
	int n,i;
	fin=fopen("huffman.in","r");
	fout=fopen("huffman.out","w");
    fscanf(fin, "%d", &n);
	nhp=n;
	for (i=0; i<n; i++)
	{
		fscanf(fin, "%d", &a[i].val);
		a[i].f[0]=a[i].f[1]=NULL;
		hp[i]=a+i;
	}
	for (i=0; i<n-1; i++)
	{
		nod * min1 = hp_popmin();
		nod * min2 = hp_popmin();
		nod * tata = &t[nt++];
		tata->val=min1->val+min2->val;
		tata->f[0]=min1;
		tata->f[1]=min2;
		tata->b=0;
		tata->lg=0;
		hp_push(tata);
	}
	dfs(&t[nt-1]);
	fprintf(fout, "%lld\n",sum);
	for (i=0; i<n; i++)
		fprintf(fout, "%d %lld\n",a[i].lg,a[i].b);
	fclose(fin);
	fclose(fout);
    return 0;
}