#include <fstream>
using namespace std;

const int nmax=1000010;
long long cod[nmax];
int lungimea[nmax];
int heap[2*nmax];

struct nod{
   int frecv;
   int f1,f2;
}nodul[2*nmax];
long long suma=0;

void df(int ind,int nivel, int codul){
   if(nodul[ind].f1==-1){
     //adica daca nodul ind este frunza
     lungimea[ind]=nivel;
     cod[ind]=codul;
     suma+=nivel*nodul[ind].frecv;
     return;
   }
   df(nodul[ind].f1,nivel+1,codul<<1);
   df(nodul[ind].f2,nivel+1,(codul<<1)| 1);
}

void urca(int loc){
   int x;
   int aux;
   while((x=loc/2) && nodul[heap[loc]].frecv<nodul[heap[x]].frecv){
      //interschimb nodul de pe locul loc cu tatal sau
      aux=heap[loc];
      heap[loc]=heap[x];
      heap[x]=aux;
      loc=x;
   }
}

int N=0;

void coboara(int loc){
   //cobor in fiul cel mai mic dintre cei doi
    int aux, x, y = 0;
    while (loc != y){
	y = loc;
	if ((x=y*2)<=N && nodul[heap[loc]].frecv>nodul[heap[x]].frecv) loc = x;
        x++;
	if (x<=N && nodul[heap[loc]].frecv>nodul[heap[x]].frecv) loc = x;
          aux = heap[loc];
	  heap[loc] = heap[y];
	  heap[y] = aux;
	}
}

int main(){
  ifstream fin("huffman.in");
  int n;
  fin>>n;
  int i;
  //am N noduri in heap
  for(i=0;i<n;i++){
    fin>>nodul[i].frecv;
    nodul[i].f1=nodul[i].f2=-1;
    //inserez indicele nodului i (adica i) in heap
    heap[++N]=i;
    urca(N);
  }
  int indice=n;//indicele curent in vectorul de noduri
  int a,b,c;
  while(N>1){
    //extrag a,b cele doua minime 
    a=heap[1];
    heap[1]=heap[N];N--;
    coboara(1);
    b=heap[1];
    heap[1]=heap[N];N--;
    coboara(1);
    //le scot din heap
    nodul[indice].f1=a;
    nodul[indice].f2=b;
    nodul[indice].frecv=nodul[a].frecv+nodul[b].frecv;
    //inserez in heap indice; heapul e min-heap dupa nodul[indice].frecv
    heap[++N]=indice;
    urca(N);
    indice++;
  }
  //dupa ce am terminat de construit arborele, il parcurg si obtin codurile
  df(indice-1,0,0);//indicele nodului,nivelul,codul
  ofstream fout("huffman.out");
  fout<<suma<<'\n';
  for(i=0;i<n;i++){
    fout<<lungimea[i]<<" "<<cod[i]<<'\n';
  }
return 0;
}