#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[1000005];
long long st[2000001];
int soll[1000005],n,poz[2000001];
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]=2*s; soll[arb[nod].l]=lev+1;} else dfs(arb[nod].l-n,s*2,lev+1);
       if (arb[nod].r<=n){solx[arb[nod].r]=s*2+1; soll[arb[nod].r]=lev+1;} else dfs(arb[nod].r-n,s*2+1,lev+1); 
}

int main(void){
    int i,j,x,cap,coada,l,nrnod=0,pas=1;
     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; 
                    }
     i=3; cap=1; coada=1; st[coada]=a[1].v+a[2].v; sum=st[coada]; 
                           poz[coada]=nrnod+1+n; ++nrnod; arb[nrnod].l=a[1].poz; arb[nrnod].r=a[2].poz;  
     a[n+1].v=10000000000000LL;
     while (pas<n-1) {
           long long v1=0,v2=0; int p1,p2;
           if (st[cap]<=a[i].v&&cap<=coada){v1=st[cap]; p1=poz[cap]; ++cap; }
                           else {v1=a[i].v; p1=a[i].poz; ++i;}
           if (st[cap]<=a[i].v&&cap<=coada){v2=st[cap]; p2=poz[cap]; ++cap; }
                           else {v2=a[i].v; p2=a[i].poz; ++i;}
              sum+=v1+v2;
               ++coada; st[coada]=v1+v2; ++nrnod;
                poz[coada]=nrnod+n; arb[nrnod].l=p1; arb[nrnod].r=p2;

           pas+=1;
          }
     fout<<sum<<"\n";
    dfs(nrnod,0,0);
     for (i=1; i<=n; ++i) fout<<soll[i]<<" "<<solx[i]<<"\n";
  return(0);
}