#include<fstream.h>
#define N 2000001
typedef struct nod
{long info,val;
nod *st,*dr;}Nod;
long long lg=0;
long n,i,j,k,q2[N],q3[N];
unsigned int q1[N];
Nod *p[N],*l;
int main()
{ifstream f1("huffman.in");
ofstream f2("huffman.out");
f1>>n;
for(i=1;i<=n;i++)
       {f1>>q1[i];
       q2[i]=N;
       q3[i]=0;
       p[i]=new Nod;
       p[i]->info=q1[i];
       p[i]->val=i;
       p[i]->st=p[i]->dr=NULL;}
j=k=1,q2[0]=0;
for(i=1;i<n;i++)
if(k<=n)
        {p[i+n]=new Nod;
        if(q1[k+1]<=q2[j]*1000+q3[j]&&k+1<=n)
                 {q2[i]=(q1[k]+q1[k+1])/1000;
                 q3[i]=(q1[k]+q1[k+1])%1000;
                 p[i+n]->st=p[k];
                 p[i+n]->dr=p[k+1];
                 k+=2;}
        else
                 if(q2[j+1]*1000+q3[j+1]<=q1[k])
                           {q2[i]=q2[j]+q2[j+1]+(q3[j]+q3[j+1])/1000;
                           q3[i]=(q3[j]+q3[j+1])%1000;
                           p[i+n]->st=p[j+n];
                           p[i+n]->dr=p[j+1+n];
                           j+=2;}
                 else
                           if(q2[j]*1000+q3[j]<=q1[k]&&q1[k]<=q2[j+1]*1000+q3[j+1])
                                    {q2[i]=(q1[k]+1000*q2[j]+q3[j])/1000;
                                    q3[i]=(q1[k]+1000*q2[j]+q3[j])%1000;
                                    p[i+n]->st=p[j+n];
                                    p[i+n]->dr=p[k];
                                    j++;
                                    k++;}
                           else
                                    if(q1[k]<=q2[j]*1000+q3[j]&&((q2[j]*1000+q3[j]<=q1[k+1]&&k+1<=n)||k+1>n))
                                             {q2[i]=(q1[k]+1000*q2[j]+q3[j])/1000;
                                             q3[i]=(q1[k]+1000*q2[j]+q3[j])%1000;
                                             p[i+n]->st=p[k];
                                             p[i+n]->dr=p[j+n];
                                             j++;
                                             k++;}
        p[i+n]->info=q2[i]*1000+q3[i];
        p[i+n]->val=i+n;
        lg=lg+(long long)q2[i]*1000+q3[i];}
else
        {q2[i]=q2[j]+q2[j+1]+(q3[j]+q3[j+1])/1000;
        q3[i]=(q3[j]+q3[j+1])%1000;
        lg=lg+(long long)q2[i]*1000+q3[i];
        p[i+n]=new Nod;
        p[i+n]->info=1000*q2[i]+q3[i];
        p[i+n]->val=i+n;
        p[i+n]->st=p[j+n];
        p[i+n]->dr=p[j+1+n];
        j+=2;}
f2<<lg<<"\n";
l=p[2*n-1];
k=j=i=0;
p[j++]=l;
q2[l->val]=q1[l->val]=q3[l->val]=0;
while(k<j)
        {l=p[k++];
        if(l->st)
                 {q1[l->st->val]=q1[l->val]+1;
                 q2[l->st->val]=2*((long long)q2[l->val]*1000+q3[l->val])/1000;
                 q3[l->st->val]=(2*((long long)q2[l->val]*1000+q3[l->val]))%1000;
                 p[j++]=l->st;}
        if(l->dr)
                 {q1[l->dr->val]=q1[l->val]+1;
                 q2[l->dr->val]=(2*((long long)q2[l->val]*1000+q3[l->val])+1)/1000;
                 q3[l->dr->val]=(2*((long long)q2[l->val]*1000+q3[l->val])+1)%1000;
                 p[j++]=l->dr;}}
for(j=1;j<=n;j++)
        f2<<q1[j]<<" "<<((long long)q2[j]*1000+q3[j])<<"\n";
f1.close();
f2.close();
return 0;}