#include<fstream.h>
#include<stdlib.h>
#define N 1000001
typedef struct nod
{unsigned long long info,val;
struct nod *st,*dr;}Nod;
typedef struct st
{Nod *elem;
struct st *urm;}el;
typedef struct
{el *prim,*ultim;}coada;
unsigned long long b[2*N],lg=0,q2[N];
long n,i,j,q1[N],k,t,a[2*N];
Nod *r[N],*p[N],*l;
coada q;

void add(coada &q,Nod *l)
{el *px=new el;
px->elem=l;
px->urm=NULL;
if(q.prim==NULL)
       q.prim=q.ultim=px;
else
       {q.ultim->urm=px;
       q.ultim=px;}}
       
Nod *del(coada &q)
{el *t=q.prim->urm;
Nod *x=q.prim->elem;
free(q.prim);
q.prim=t;
if(q.prim==NULL)
       q.ultim=NULL;
return x;}

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.prim=q.ultim=NULL;
add(q,r[t]);
b[r[t]->val]=a[r[t]->val]=0;
while(q.prim)
        {l=del(q);
        if(l->st)
                 {a[l->st->val]=a[l->val]+1;
                 b[l->st->val]=2*b[l->val];
                 add(q,l->st);}
        if(l->dr)
                 {a[l->dr->val]=a[l->val]+1;
                 b[l->dr->val]=2*b[l->val]+1;
                 add(q,l->dr);}}
for(i=1;i<=n;i++)
        f2<<a[i]<<" "<<b[i]<<"\n";
f1.close();
f2.close();
return 0;}