#include <fstream>
#include <vector>

struct Node{
	unsigned long long w;
	unsigned f[2];
	Node(){w=0;f[0]=0;f[1]=0;}
};

void df(unsigned poz, unsigned curr, unsigned cniv,
		std::vector<unsigned> &nivel, std::vector<unsigned> &cod, const std::vector<Node> &nod){
	if(nod[poz].f[0]!=0){
		df(nod[poz].f[0],curr<<1,cniv+1,nivel,cod,nod);
		df(nod[poz].f[1],(curr<<1)+1,cniv+1,nivel,cod,nod);

	}
	else{
		cod[poz]=curr;
		nivel[poz]=cniv;
	}
}


int main(){
	std::ifstream fin("huffman.in");
	std::ofstream fout("huffman.out");

	unsigned n; fin>>n;
	std::vector<Node> nod(2*n);
	unsigned cn=1;

	std::vector<unsigned> q[2];
	q[0].resize(n+1); q[1].resize(n+1);
	unsigned a[2]={1,1}, b[2]={0,0};
	unsigned ord=0; //q[ord]=prima coada, q[1-ord]=a doua coada


	for(;cn<=n;++cn){
		q[ord][++b[ord]]=cn;
		fin>>nod[cn].w;
	}

	while(a[ord]<b[ord]){ //minim doua noduri
		while(a[ord]<=b[ord]){
			unsigned m[2];

			for(unsigned i=0;i<2;++i)
				if((nod[q[ord][a[ord]]].w<nod[q[1-ord][a[1-ord]]].w&&a[ord]<=b[ord])||a[1-ord]>b[1-ord]){ m[i]=q[ord][a[ord]]; a[ord]++; }
				else{ m[i]=q[1-ord][a[1-ord]]; a[1-ord]++; }

			nod[cn].w=nod[m[0]].w+nod[m[1]].w;
			nod[cn].f[0]=m[0];
			nod[cn].f[1]=m[1];
			q[1-ord][++b[1-ord]]=cn;
			cn++;
		}
		a[ord]=1; b[ord]=0;
		ord=1-ord;
	}

	std::vector<unsigned> nivel(n+1);
	std::vector<unsigned> cod(n+1);

	df(q[ord][a[ord]],0,0,nivel,cod,nod);


	unsigned lgtot=0;
	for(unsigned i=1;i<=n;++i) lgtot+=nod[i].w*nivel[i];

	fout<<lgtot<<'\n';
	for(unsigned i=1;i<=n;++i) fout<<nivel[i]<<' '<<cod[i]<<'\n';
}