#include<fstream.h>
#define N 1000001
#define INF 1000000000
typedef struct nod
{long info,val;
nod *st,*dr;}Nod;
long long lg=0,q2[N];
long n,i,j,k,t,prim=0,ultim=0,a1[2*N],a2[2*N],a3[2*N];
unsigned int a[2*N],q1[N];
Nod *r[N],*p[N],*l,*q[2*N];

Nod *make(long x,long y,Nod *left,Nod *right)
{Nod *r=new Nod;
r->info=x;
r->val=y;
r->st=left;
r->dr=right;
return r;}

int main()
{ifstream f1("huffman.in");
ofstream f2("huffman.out");
f1>>n;
for(i=1;i<=n;i++)
       {f1>>q1[i];
       q2[i]=N;
       p[i]=make(q1[i],i,NULL,NULL);}
j=k=1,t=0;
for(i=1;i<n;i++)
if(k<=n)
        {if(q1[k+1]<=q2[j]&&k+1<=n)
                 {q2[++t]=q1[k]+q1[k+1];
                 r[t]=make(q2[t],t+n,p[k],p[k+1]);
                 k+=2;}
        else
                 if(q2[j+1]<=q1[k])
                           {q2[++t]=q2[j]+q2[j+1];
                           r[t]=make(q2[t],t+n,r[j],r[j+1]);
                           j+=2;}
                 else
                           if(q2[j]<=q1[k]&&q1[k]<=q2[j+1])
                                    {q2[++t]=q1[k]+q2[j];
                                    r[t]=make(q2[t],t+n,r[j],p[k]);
                                    j++;
                                    k++;}
                           else
                                    if(q1[k]<=q2[j]&&((q2[j]<=q1[k+1]&&k+1<=n)||k+1>n))
                                             {q2[++t]=q1[k]+q2[j];
                                             r[t]=make(q2[t],t+n,p[k],r[j]);
                                             j++;
                                             k++;}
        lg+=q2[t];}
else
        {q2[++t]=q2[j]+q2[j+1];
        lg+=q2[t];
        r[t]=make(q2[t],t+n,r[j],r[j+1]);
        j+=2;}
f2<<lg<<"\n";
q[ultim++]=r[t];
a[r[t]->val]=a1[r[t]->val]=0;
while(prim<ultim)
        {l=q[prim++];
        if(l->st)
                 {a[l->st->val]=a[l->val]+1;
                 if((a1[l->val]<<1)>INF)
                          {a1[l->st->val]=a1[l->val];
                          a2[l->st->val]=a2[l->val]<<1;
                          a3[l->st->val]=a3[l->val]<<1;}
                 else
                          {a1[l->st->val]=a1[l->val]<<1;
                          a2[l->st->val]=1,a3[l->st->val]=0;}
                 q[ultim++]=l->st;}
        if(l->dr)
                 {a[l->dr->val]=a[l->val]+1;
                 if((a1[l->val]<<1)>INF)
                          {a1[l->dr->val]=a1[l->val];
                          a2[l->dr->val]=a2[l->val]<<1;
                          a3[l->dr->val]=(a3[l->val]<<1)+1;}
                 else
                          {a1[l->dr->val]=(a1[l->val]<<1)+1;
                          a2[l->dr->val]=1,a3[l->dr->val]=0;}
                 q[ultim++]=l->dr;}}
for(i=1;i<=n;i++)
        f2<<a[i]<<" "<<(long long)a1[i]*a2[i]+a3[i]<<"\n";
f1.close();
f2.close();
return 0;}