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

#define TRUE  1
#define FALSE 0

typedef char byte;

typedef struct 
{
    void* parent;
    byte  isLeft;
    int   occurences;
} Letter;

void SiftDown(Letter** letterHeap, int heapLength, int position)
{
    Letter** heapInUse = letterHeap - 1;
    if(position <= heapLength)
    {
        int next1 = position * 2;
        int next2 = next1 + 1;

        if(next1 <= heapLength)
        {
            int bestIndex = next1;

            if(next2 <= heapLength)
            {
                if(heapInUse[next2]->occurences < heapInUse[bestIndex]->occurences)
                {
                    bestIndex = next2;
                }
            }

            if(heapInUse[bestIndex]->occurences < heapInUse[position]->occurences)
            {
                Letter* tmp = heapInUse[bestIndex];
                heapInUse[bestIndex] = heapInUse[position];
                heapInUse[position] = tmp;

                SiftDown(letterHeap, heapLength, bestIndex);
            }
        }
    }
}

Letter* DeleteBest(Letter** letterHeap, int* heapLength)
{
    Letter** heapInUse = letterHeap - 1;
    Letter* result = heapInUse[1];

    heapInUse[1] = heapInUse[*heapLength];
    (*heapLength)--;
    SiftDown(letterHeap, *heapLength, 1);

    return result;
}

void Percolate(Letter** letterHeap, int heapLength, int position)
{
    Letter** heapInUse = letterHeap - 1;
    if(position >= 1)
    {
        int prevPos = position / 2;
        if(prevPos >= 1)
        {
            if(heapInUse[position]->occurences < heapInUse[prevPos]->occurences)
            {
                Letter* tmp = heapInUse[position];
                heapInUse[position] = heapInUse[prevPos];
                heapInUse[prevPos] = tmp;

                Percolate(letterHeap, heapLength, prevPos);
            }
        }
    }
}

void InsertLetter(Letter** letterHeap, Letter* letter, int* heapLength)
{
    Letter** heapInUse = letterHeap - 1;

    (*heapLength)++;
    heapInUse[*heapLength] = letter;

    Percolate(letterHeap, *heapLength, *heapLength);
}

unsigned long long Huffman(Letter** letterHeap, int* heapLength)
{
    unsigned long long result = 0;

    while((*heapLength) != 1)
    {
        Letter* firstBest = DeleteBest(letterHeap, heapLength);
        Letter* secondBest = DeleteBest(letterHeap, heapLength);

        Letter* mergedLetter = (Letter*)malloc(sizeof(Letter));
        mergedLetter->occurences = firstBest->occurences + secondBest->occurences;
        mergedLetter->parent = NULL;
        mergedLetter->isLeft = FALSE;

        firstBest->parent = mergedLetter;
        firstBest->isLeft = TRUE;

        secondBest->parent = mergedLetter;
        secondBest->isLeft = FALSE;

        result += mergedLetter->occurences;

        InsertLetter(letterHeap, mergedLetter, heapLength);
    }

    return result;
}

void ShowLetter(FILE* fout, Letter* letter, int accumNumber, int index)
{
    if(letter->parent != NULL)
    {
        accumNumber += letter->isLeft << index;
        ShowLetter(fout, (Letter*)letter->parent, accumNumber, index + 1);
    }
    else
    {
        fprintf(fout, "%d %d\n", index, accumNumber);
    }
    
}

int main(void)
{
    FILE* fin = fopen("huffman.in", "r");
    FILE* fout = fopen("huffman.out", "w");
    int i;
    int n;
    int heapLength = 0;
    Letter** codeLetters;
    Letter** letterHeap;

    fscanf(fin, "%d", &n);
    heapLength = n;
    
    codeLetters = (Letter**)malloc(sizeof(Letter*) * n);
    letterHeap = (Letter**)malloc(sizeof(Letter*) * n);

    for(i = 0; i < n; i++)
    {
        int occurences;
        fscanf(fin, "%d", &occurences);

        codeLetters[i] = (Letter*)malloc(sizeof(Letter));
        codeLetters[i]->parent = NULL;
        codeLetters[i]->occurences = occurences;
        codeLetters[i]->isLeft = FALSE;

        letterHeap[i] = codeLetters[i];
    }

    fprintf(fout, "%llu\n", Huffman(letterHeap, &heapLength));

    for(int i = 0 ; i < n; i++)
    {
        ShowLetter(fout, codeLetters[i], 0, 0);
    }

    for(i = 0; i < n; i++)
    {
        free(codeLetters[i]);
        codeLetters[i] = NULL;
        letterHeap[i] = NULL;
    }

    free(codeLetters);
    codeLetters = NULL;
    free(letterHeap);
    letterHeap = NULL;

    fclose(fin);
    fclose(fout);

    return 0;
}