#include<fstream.h>
#include<stdlib.h>
#define N 1000001
typedef struct nod
{unsigned long long info;
long val;
nod *st,*dr;}Nod;
typedef struct st
{Nod *elem[2*N];
long 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;

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