#include<fstream>
#include<iostream>
#include<vector>
#include<string>

using namespace std;
ifstream in("huffman.in");
ofstream out("huffman.out");
#define inf	1000000000000000000LL
long long lg;

struct frunza{
	int id;
	int f;
	frunza *next;
	void *adr;
};

struct nod_intern{
	long long f;
	nod_intern *next;
	void *adr;
};

struct nod{
	long long f;
	//int id;
	nod *stg, *dr, *up;
};

struct car{
	int lung;
	nod *adr_nod_f;
	string s;
	long long cod;
};

struct lista_frunze{
	frunza *vf,*sf;
};

struct lista_nod_intern{
	nod_intern *vf;
};

struct lista_nod{
	nod *vf,*sf;
};

int n;
lista_frunze lf;
lista_nod_intern lni;
vector<car> vc;
nod *vf_arb;

nod* add_nod(long long f, nod* stg, nod* dr, nod* up){
	nod *n=new(nod);
	n->f=f;
	n->stg=stg;
	n->dr=dr;
	n->up=up;
	return n;
}

void add_lf(int id, int f){
	frunza *n=new(frunza);
	n->id=id;
	n->f=f;
	n->next=NULL;
	n->adr=add_nod(f,NULL,NULL,NULL);
	car n_c;
	n_c.adr_nod_f=(nod*)(n->adr);
	vc.push_back(n_c);
	if(!lf.vf)
		lf.vf=n;
	else
		lf.sf->next=n;
	lf.sf=n;
}

void init_lni(){
	nod_intern *n=new(nod_intern);
	n->f=inf;
	n->next=NULL;
	lni.vf=n;
}

void insert_lni(long long f, nod* stg, nod* dr, nod* up){
	nod_intern *nc=lni.vf;
	nod_intern *n=new(nod_intern);
	n->f=f;
	lg+=f;
	if(f<=nc->f){
		n->next=nc;
		lni.vf=n;
		n->adr=add_nod(f,stg,dr,up);
		vf_arb=(nod*)n->adr;
		stg->up=(nod*)n->adr;
		dr->up=(nod*)n->adr;
		return;
	}
	while(nc->next->f<f)
		nc=nc->next;
	n->next=nc->next;
	nc->next=n;
	n->adr=add_nod(f,stg,dr,up);
	vf_arb=(nod*)n->adr;
	stg->up=(nod*)n->adr;
	dr->up=(nod*)n->adr;
}

void afis_lf(){
	frunza *nc=lf.vf;
	while(nc){
		out<<nc->id<<"\t"<<nc->f<<"\n";
		nc=nc->next;
	}
	out<<"\n";
}

void afis_lni(){
	nod_intern *nc=lni.vf;
	while(nc->f<inf){
		out<<nc->f<<" ";
		nc=nc->next;
	}
	out<<"\n*******\n";
}

/*
nod* add_nod(int id, long long f, nod* stg, nod* dr){
	nod *n=new(nod);
	n->id=id;
	n->f=f;
	n->stg=stg;
	n->dr=dr;
	return n;
}
*/
void create_lni(){
	init_lni();
	frunza *nf;
	nod_intern *ni;
	long long f1,f2;
	nod *stg,*dr;
	while(1){
		nf=lf.vf;
		ni=lni.vf;
		if(ni->f<nf->f){
			f1=ni->f;
			stg=(nod*)ni->adr;
			nod_intern *temp=ni;
			lni.vf=ni->next;
			delete temp;
		}
		else{
			f1=nf->f;
			stg=(nod*)nf->adr;
			frunza *temp=nf;
			lf.vf=nf->next;
			delete temp;
		}
		nf=lf.vf;
		ni=lni.vf;
		if(ni->f<nf->f){
			f2=ni->f;
			dr=(nod*)ni->adr;
			nod_intern *temp=ni;
			lni.vf=ni->next;
			delete temp;
		}
		else{
			f2=nf->f;
			dr=(nod*)nf->adr;
			frunza *temp=nf;
			lf.vf=nf->next;
			delete temp;
		}
		insert_lni(f1+f2,stg,dr,NULL);
		//afis_lf();
		//afis_lni();
		if(!lf.vf)
			break;
	}
	while(lni.vf->f<inf){
		ni=lni.vf;
		f1=ni->f;
		stg=(nod*)ni->adr;
		lni.vf=ni->next;
		delete ni;
		if(lni.vf->f<inf){
			ni=lni.vf;
			f2=ni->f;
			dr=(nod*)ni->adr;
			lni.vf=ni->next;
			delete ni;
		}
		else
			f2=0;
		if(f2){
			insert_lni(f1+f2,stg,dr,NULL);
			//afis_lni();
		}
	}
}



int lung(nod* nc){
	if(!nc)
		return 0;
	return lung(nc->up)+1;
}
void cod(nod* nc, nod* na, string &s){
	if(!nc)
		s="";
	else{
		cod(nc->up,nc,s);
		if(na==nc->stg)
			s+='0';
		else
			s+='1';
	}
}

long long cod_10(string s){
	long long r=0LL;
	for(int i=s.length()-1;i>=0;i--)
		if(s[i]=='1')
			r+=(1<<(s.length()-i-1));
	return r;
}
void calc_lung_cod(){
	for(int i=1;i<(int)vc.size();++i){
		nod *nc=vc[i].adr_nod_f;
		vc[i].lung=lung(nc->up);
		string s;
		cod(nc->up,nc,s);
		vc[i].s=s;
		vc[i].cod=cod_10(s);
	}
}
int main(){
	int f;
	in>>n;
	//citire
	vc.resize(0);
	car n_c;
	vc.push_back(n_c);
	for(int i=0;i<n;++i){
		in>>f;
		add_lf(i,f);
		lg+=f;
	}
	//afis_li();
	create_lni();
	//afis_lni();
	out<<lg-vf_arb->f<<"\n";
	calc_lung_cod();
	for(int i=1;i<=n;++i)
		out<<vc[i].lung<<" "/*<<vc[i].s<<" "*/<<vc[i].cod<<"\n";
	return 0;
}