#include<fstream.h>
#define N 2000000
long long q2[N];
long n,i,j,k,r[N],x[N],st[N],dr[N],l;
unsigned int q1[N];
int main()
{ifstream f1("huffman.in");
ofstream f2("huffman.out");
f1>>n;
for(i=1;i<=n;i++)
       {f1>>q1[i];
       q2[i]=N;
       x[i]=i;
       r[i]=q1[i];
       st[i]=dr[i]=0;}
j=k=1,q2[0]=0;
for(i=1;i<n;i++)
       {if(k<=n)
                {if(q1[k+1]<=q2[j]&&k+1<=n)
                          {q2[i]=q1[k]+q1[k+1];
                          st[i+n]=k;
                          dr[i+n]=k+1;
                          k+=2;}
                else
                          if(q2[j+1]<=q1[k])
                                    {q2[i]=q2[j]+q2[j+1];
                                    st[i+n]=j+n;
                                    dr[i+n]=j+1+n;
                                    j+=2;}
                          else
                                    if(q2[j]<=q1[k]&&q1[k]<=q2[j+1])
                                             {q2[i]=q1[k]+q2[j];
                                             st[i+n]=j+n;
                                             dr[i+n]=k;
                                             j++,k++;}
                                    else
                                             if(q1[k]<=q2[j]&&((q2[j]<=q1[k+1]&&k+1<=n)||k+1>n))
                                                       {q2[i]=q1[k]+q2[j];
                                                       st[i+n]=k;
                                                       dr[i+n]=j+n;
                                                       j++,k++;}}
       else
                {q2[i]=q2[j]+q2[j+1];
                st[i+n]=j+n;
                dr[i+n]=j+1+n;
                j+=2;}
       q2[0]+=q2[i];
       r[i+n]=q2[i];
       x[i+n]=i+n;}
f2<<q2[0]<<"\n";
l=2*n-1;
k=j=q2[l]=q1[l]=0;
r[j++]=l;
while(k<j)
        {l=r[k++];
        if(st[l])
                 {q1[x[st[l]]]=q1[x[dr[l]]]=q1[x[l]]+1;
                 q2[x[st[l]]]=q2[x[l]]<<1;
                 q2[x[dr[l]]]=(q2[x[l]]<<1)+1;
                 if(x[l]>n)
                          {r[j++]=st[l];
                          r[j++]=dr[l];}}}
for(i=1;i<=n;i++)
        f2<<q1[i]<<" "<<q2[i]<<"\n";
f1.close();
f2.close();
return 0;}