#include<fstream>
#include<string>
using namespace std;
typedef struct w{int l,r;}tip;
typedef struct q{long long v; int poz;}tip2;
tip arb[1000005];
tip2 a[1000001],st[1000001];
int soll[1000001],n;
long long sum,solx[1000001];
string s;

ifstream fin("huffman.in");
 ofstream fout("huffman.out");
 
inline void dfs(int nod,long long s,int lev){
       if (arb[nod].l<=n){solx[arb[nod].l]=s; soll[arb[nod].l]=lev;} else dfs(arb[nod].l,s*2,lev+1);
       if (arb[nod].r<=n){solx[arb[nod].r]=s*2+1; soll[arb[nod].r]=lev;} else dfs(arb[nod].r,s*2+1,lev+1); 
}

int main(void){
    int i,j,x,cap,coada,l,nrnod=0;
     fin>>n; getline(fin,s); n=0;
       getline(fin,s,char(EOF)); i=j=0; l=s.length();
        while(j<l) {    
                    x=0;
                    while(s[j]!='\n' && j<l)x=(x*10)+(s[j++]-'0');
                    a[++n].v=x; a[n].poz=n; ++j; arb[n].l=arb[n].r=0;
                    } 
     i=3; cap=1; coada=1; st[coada].v=a[1].v+a[2].v; sum=st[coada].v;
                           st[coada].poz=nrnod+1; ++nrnod; arb[nrnod].l=a[1].poz; arb[nrnod].r=a[2].poz;  
     a[n+1].v=10000000000000LL;
     while (i<=n+1) {
           if ( st[cap].v<=a[i].v&&cap<=coada ) {--i; a[i]=st[cap]; ++cap;}
           if ( st[cap].v<=a[i+1].v&&cap<=coada ) {--i; a[i]=a[i+1]; a[i+1]=st[cap]; ++cap;}
           if (i<n){
              sum+=a[i].v+a[i+1].v;
               ++coada; st[coada].v=a[i].v+a[i+1].v; ++nrnod;
               st[coada].poz=nrnod; arb[nrnod].l=a[i].poz; arb[nrnod].r=a[i+1].poz;
               }
           i=i+2;
          }
     fout<<sum<<"\n";
    dfs(nrnod,0,0);
    for (i=1; i<=n; ++i) fout<<soll[i]<<" "<<solx[i]<<"\n";
  return(0);
}