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

#define BIAS  5
#define TRUE  1
#define FALSE 0

typedef char               byte;
typedef unsigned long long LLU;

typedef struct 
{
    int  parent;
    byte isLeft;
} Node;

typedef struct
{
    int   indexInTree;
    LLU   occurences;
    void* next;
} QueueNode;

void AddElementToQueue(QueueNode** queue, QueueNode** lastElementQueue, QueueNode* element)
{
    if((*lastElementQueue) == NULL)
    {
        *queue = element;
        *lastElementQueue = *queue;
    }
    else
    {
        (*lastElementQueue)->next = (void*)element;
        *lastElementQueue = element;
    }
}

void PopQueue(QueueNode** queue)
{
    QueueNode* next = (QueueNode*)(*queue)->next;
    free(*queue);
    *queue = next;
}

LLU Huffman(Node* tree, 
            QueueNode** pureQueue, 
            QueueNode** lastElementPureQueue,
            QueueNode** mergedQueue,
            QueueNode** lastElementMergedQueue,
            int n)
{
    LLU result = 0;
    int i;
    int indexToAdd = n;
    byte stop = FALSE;

    while(!stop)
    {
        if(*pureQueue == NULL && *mergedQueue != NULL)
        {
            if((*mergedQueue)->next == NULL)
            {
                stop = TRUE;
                continue;
            }
        }

        QueueNode* chosenQueueNodes[] = {NULL, NULL, NULL, NULL};
        
        chosenQueueNodes[0] = (*pureQueue);
        if(*pureQueue)
            chosenQueueNodes[1] = (QueueNode*)(*pureQueue)->next;
        chosenQueueNodes[2] = (*mergedQueue);
        if(*mergedQueue)
            chosenQueueNodes[3] = (QueueNode*)(*mergedQueue)->next;
        
        int smallestIndex = -1;
        int secondSmallest = -1;

        for(i = 0; i < 4; i++)
        {
            if(chosenQueueNodes[i] != NULL)
            {
                byte isSmallest = FALSE;

                if(smallestIndex == -1)
                {
                    isSmallest = TRUE;
                }
                else
                {
                    if(chosenQueueNodes[smallestIndex]->occurences > chosenQueueNodes[i]->occurences)
                    {
                        isSmallest = TRUE;
                    }
                }

                if(isSmallest)
                {
                    smallestIndex = i;
                }
            }
        }

        for(int i = 0; i < 4; i++)
        {
            if(i != smallestIndex)
            {
                if(chosenQueueNodes[i] != NULL)
                {
                    byte isSmallest = FALSE;
                    if(secondSmallest == -1)
                    {
                        isSmallest = TRUE;
                    }
                    else
                    {
                        if(chosenQueueNodes[secondSmallest]->occurences > chosenQueueNodes[i]->occurences)
                        {
                            isSmallest = TRUE;
                        }
                    }
                    
                    if(isSmallest)
                    {
                        secondSmallest = i;
                    }
                }
            }
        }

        if(secondSmallest != -1 && smallestIndex != -1 && secondSmallest != smallestIndex)
        {
            QueueNode* child1 = chosenQueueNodes[smallestIndex];
            QueueNode* child2 = chosenQueueNodes[secondSmallest];

            tree[child1->indexInTree].parent = indexToAdd;
            tree[child1->indexInTree].isLeft = TRUE;

            tree[child2->indexInTree].parent = indexToAdd;
            tree[child2->indexInTree].isLeft = FALSE;

            tree[indexToAdd].parent = indexToAdd;
            
            QueueNode* queueNode = (QueueNode*)malloc(sizeof(QueueNode));
            queueNode->indexInTree = indexToAdd;
            queueNode->next = NULL;
            queueNode->occurences = child1->occurences + child2->occurences;

            result += queueNode->occurences;

            AddElementToQueue(mergedQueue, lastElementMergedQueue, queueNode);

            indexToAdd++;

            if(smallestIndex <= 1)
                PopQueue(pureQueue);
            else
                PopQueue(mergedQueue);
            
            if(secondSmallest <= 1)
                PopQueue(pureQueue);
            else
                PopQueue(mergedQueue);
        }
    }

    return result;
}

void ShowCharacter(FILE* fout, Node* tree, int indexInTree, int level, int number)
{
    if(tree[indexInTree].parent == indexInTree)
    {
        fprintf(fout, "%d %d\n", level, number);
    }
    else
    {
        ShowCharacter(fout, tree, tree[indexInTree].parent, level + 1, number + (tree[indexInTree].isLeft << level));
    }
    
}

int main(void)
{
    int        i;
    int        n;

    Node*      tree;

    QueueNode* pureQueue = NULL;
    QueueNode* lastElementPureQueue = NULL;

    QueueNode* mergedQueue = NULL;
    QueueNode* lastElementMergedQueue = NULL;

    FILE* fin = fopen("huffman.in", "r");
    FILE* fout = fopen("huffman.out", "w");

    fscanf(fin, "%d", &n);
    tree = (Node*)malloc(sizeof(Node) * (n + BIAS) * 2);

    for(i = 0; i < n; i++)
    {
        tree[i].parent = i;
        tree[i].isLeft = FALSE;

        QueueNode* queueNode = (QueueNode*)malloc(sizeof(QueueNode));
        queueNode->indexInTree = i;
        queueNode->next = NULL;
        fscanf(fin, "%llu", &queueNode->occurences);

        AddElementToQueue(&pureQueue, &lastElementPureQueue, queueNode);
    }

    fprintf(fout, "%llu\n", Huffman(tree, &pureQueue, &lastElementPureQueue, &mergedQueue, &lastElementMergedQueue, n));

    for(int i = 0; i < n; i++)
    {
        ShowCharacter(fout, tree, i, 0, 0);
    }

    // let the TREE
    // be FREE
    free(tree);
    tree = NULL;

    fclose(fin);
    fclose(fout);

    return 0;
}