#include<fstream.h>
#define N 2000000
long long q[N];
long n,i,j,k,r[N],x[N],s[N],d[N];
unsigned int p[N];
int main()
{ifstream f("huffman.in");
ofstream g("huffman.out");
f>>n;
for(i=1;i<=n;i++)
       {f>>p[i];
       q[i]=N,x[i]=i;
       r[i]=p[i],s[i]=d[i]=0;}
j=k=1,q[0]=0;
for(i=1;i<n;i++)
       {if(k<=n)
                {if(p[k+1]<=q[j]&&k+1<=n)
                          {q[i]=p[k]+p[k+1];
                          s[i+n]=k,d[i+n]=k+1;
                          k+=2;}
                else
                          if(q[j+1]<=p[k])
                                    {q[i]=q[j]+q[j+1];
                                    s[i+n]=j+n,d[i+n]=j+1+n;
                                    j+=2;}
                          else
                                    if(q[j]<=p[k]&&p[k]<=q[j+1])
                                             {q[i]=p[k]+q[j];
                                             s[i+n]=j+n,d[i+n]=k;
                                             j++,k++;}
                                    else
                                             if(p[k]<=q[j]&&((q[j]<=p[k+1]&&k+1<=n)||k+1>n))
                                                       {q[i]=p[k]+q[j];
                                                       s[i+n]=k,d[i+n]=j+n;
                                                       j++,k++;}}
       else
                {q[i]=q[j]+q[j+1];
                s[i+n]=j+n,d[i+n]=j+1+n;
                j+=2;}
       q[0]+=q[i],r[i+n]=q[i],x[i+n]=i+n;}
g<<q[0]<<"\n";
i=2*n-1;
k=j=q[i]=p[i]=0;
r[j++]=i;
while(k<j)
        {i=r[k++];
        if(s[i])
                 {p[x[s[i]]]=p[x[d[i]]]=p[x[i]]+1;
                 q[x[s[i]]]=q[x[i]]<<1;
                 q[x[d[i]]]=q[x[s[i]]]+1;
                 if(x[i]>n)
                          r[j++]=s[i],r[j++]=d[i];}}
for(i=1;i<=n;i++)
        g<<p[i]<<" "<<q[i]<<"\n";
f.close();
g.close();
return 0;}