#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct nodes
{
    int value;
    struct nodes *l,*r;
}nodes;


void afis(FILE* fout, nodes* root,int cod, int lv)
{
    if(root!=NULL)
    {
        if(root->l==NULL && root->r==NULL)
            fprintf(fout,"%d %d\n",lv,cod);
        cod=cod<<1;
        lv++;
        afis(fout,root->l,cod,lv);
        afis(fout,root->r,cod+1,lv);
    }
}
void huffman(int n, nodes** frecv, nodes** costs)
{
    int i=0,j=0,t=0,sum=0;
    nodes *nr1,*nr2;
    frecv[n]=(nodes*)malloc(sizeof(nodes));
    frecv[n]->value=INT_MAX;

    while(i<n || j<t-1)
    {
        if(t!=0 && costs[j]->value<frecv[i]->value)
            nr1=costs[j++];
        else
            nr1=frecv[i++];
        if(t!=0 && costs[j]->value<frecv[i]->value)
            nr2=costs[j++];
        else
            nr2=frecv[i++];

        costs[t]=(nodes*)malloc(sizeof(nodes));
        costs[t]->value=nr1->value+nr2->value;
        sum+=costs[t]->value;
        costs[t]->l=nr1;
        costs[t++]->r=nr2;
    }
    FILE* fout=fopen("huffman.out","w");
    fprintf(fout,"%d\n",sum);
    afis(fout,costs[t-1],0,0);
    fclose(fout);
}

int main()
{
    int n,i,x;
    nodes** frecv=(nodes**)malloc(sizeof(nodes*)*1000002);
    nodes** costs=(nodes**)malloc(sizeof(nodes*)*1000002);

    FILE* fin=fopen("huffman.in","r");
    fscanf(fin,"%d",&n);
    for(i=0;i<n;i++)
    {
        frecv[i]=(nodes*)malloc(sizeof(nodes));
        fscanf(fin,"%d",&x);
        frecv[i]->value=x;
        frecv[i]->r=NULL;
        frecv[i]->l=NULL;
    }
    fclose(fin);

    huffman(n,frecv,costs);

    return 0;
}