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

#define BIAS  0
#define TRUE  1
#define FALSE 0
	
typedef char               byte;
typedef unsigned long long LLU;

typedef struct 
{
    int leftChild;
    int rightChild;
} Node;
	
typedef struct
{
    int indexInTree;
    LLU occurences;
} QueueNode;

FILE* fin;
FILE* fout;

Node* tree;
LLU*  cache;
int*  levels;
	
void AddElementToQueue(QueueNode* queue, int* right, QueueNode element)
{
    queue[(*right)++] = element;
}
	
QueueNode PopQueue(QueueNode* queue, int* left)
{
    return queue[(*left)++];
}
	
byte IsQueueEmpty(int* left, int* right)
{
    if(*left == *right)
        return TRUE;

    return FALSE;
}
	
LLU Huffman(QueueNode* pureQueue,
            QueueNode* mergedQueue,
            int* leftPureQueue,
            int* rightPureQueue,
            int* leftMergedQueue,
            int* rightMergedQueue,
            int* root,
            int n)
{
    LLU  result = 0;
    int  i;
    int  indexToAdd = n;
    byte stop = FALSE;
	
    while(!stop)
    {
        if(IsQueueEmpty(leftPureQueue, rightPureQueue) && !IsQueueEmpty(leftMergedQueue, rightMergedQueue))
        {
            if(*leftMergedQueue == (*rightMergedQueue) - 1)
            {
                stop = TRUE;
                break;
            }
        }
	
        QueueNode* chosenQueueNodes[] = {NULL, NULL, NULL, NULL};
	
        if(*leftPureQueue < (*rightPureQueue))
            chosenQueueNodes[0] = &pureQueue[*leftPureQueue];
	
        if(*leftPureQueue < (*rightPureQueue) - 1)
            chosenQueueNodes[1] = &pureQueue[*leftPureQueue + 1];
 
	
        if(*leftMergedQueue < (*rightMergedQueue))
            chosenQueueNodes[2] = &mergedQueue[*leftMergedQueue];
	
        if(*leftMergedQueue < (*rightMergedQueue) - 1)
            chosenQueueNodes[3] = &mergedQueue[*leftMergedQueue + 1];
	
        int smallestIndex = -1;
        int secondSmallest = -1;
        byte isSmallest = FALSE;
	
        for(i = 0; i < 4; i++)
        {
            if(chosenQueueNodes[i] != NULL)
            {
                isSmallest = FALSE;
	
                if(smallestIndex == -1)
                    isSmallest = TRUE;
                else
                    if(chosenQueueNodes[smallestIndex]->occurences > chosenQueueNodes[i]->occurences)
                        isSmallest = TRUE;
	
                if(isSmallest)
                    smallestIndex = i;
            }
        }
	
        for(i = 0; i < 4; i++)
        {
            if(i != smallestIndex)
            {
                if(chosenQueueNodes[i] != NULL)
                {
                    isSmallest = FALSE;
	
                    if(secondSmallest == -1)
                        isSmallest = TRUE;
                    else
                        if(chosenQueueNodes[secondSmallest]->occurences > chosenQueueNodes[i]->occurences)
                            isSmallest = TRUE;
	
                    if(isSmallest)
                        secondSmallest = i;
                }
            }
        }
	
        QueueNode* child1 = chosenQueueNodes[smallestIndex];
        QueueNode* child2 = chosenQueueNodes[secondSmallest];

        tree[indexToAdd].leftChild  = child1->indexInTree;
        tree[indexToAdd].rightChild = child2->indexInTree;

        *root = indexToAdd;

        QueueNode queueNode;
        queueNode.indexInTree = indexToAdd;
        queueNode.occurences  = child1->occurences + child2->occurences;

        result += queueNode.occurences;

        AddElementToQueue(mergedQueue, rightMergedQueue, queueNode);
        indexToAdd++;

        if(smallestIndex <= 1)
            PopQueue(pureQueue, leftPureQueue);
        else
            PopQueue(mergedQueue, leftMergedQueue);

        if(secondSmallest <= 1)
            PopQueue(pureQueue, leftPureQueue);
        else
            PopQueue(mergedQueue, leftMergedQueue);
    }
	
    return result;	
}

void GetResults(int position, LLU code, int level)
{
    if(tree[position].leftChild  == -1 && 
       tree[position].rightChild == -1)
    {
        cache[position]  = code;
        levels[position] = level;
    }
    else
    {
        GetResults(tree[position].leftChild,  (code << 1),     level+1);
        GetResults(tree[position].rightChild, (code << 1) + 1, level+1);
    }
}
 
int main(void)	
{
    int        i;
    int        n;
    int        rootPos;
	
    QueueNode* pureQueue = NULL;
	int        leftPureQueue = 0;
	int        rightPureQueue = 0;
	
    QueueNode* mergedQueue = NULL;
	int        leftMergedQueue = 0;
	int        rightMergedQueue = 0;
	
    fin  = fopen("huffman.in", "r");
    fout = fopen("huffman.out", "w");

    fscanf(fin, "%d", &n);

    tree        = (Node*)     malloc(sizeof(Node)      * (n + BIAS) * 2);
    pureQueue   = (QueueNode*)malloc(sizeof(QueueNode) * (n + BIAS));
    mergedQueue = (QueueNode*)malloc(sizeof(Node)      * (n + BIAS) * 2);

    for(i = 0; i < n; i++)
    {
        tree[i].leftChild  = -1;
        tree[i].rightChild = -1;
	
        QueueNode queueNode;
        queueNode.indexInTree = i;
	    fscanf(fin, "%llu", &queueNode.occurences);
	
        AddElementToQueue(pureQueue, 
                          &rightPureQueue, 
                          queueNode);
	}
	
    fprintf(fout, "%llu\n", Huffman(pureQueue, 
                                    mergedQueue, 
                                    &leftPureQueue, 
                                    &rightPureQueue, 
                                    &leftMergedQueue, 
                                    &rightMergedQueue, 
                                    &rootPos, 
                                    n));

    free(pureQueue);
    pureQueue = NULL;
    free(mergedQueue);
    mergedQueue = NULL;

    cache  = (LLU*)malloc(sizeof(LLU) * (n + BIAS));
    levels = (int*)malloc(sizeof(int) * (n + BIAS));

    GetResults(rootPos, 0LL, 0);

    for(i = 0; i < n; i++)
    {
        fprintf(fout, "%d %llu\n", levels[i], cache[i]);
    }

    free(cache);
    cache = NULL;
    free(levels);
    levels = NULL;
	
    // Let the TREE
    // Be FREE
    free(tree);
    tree = NULL;
	
    fclose(fin);
    fclose(fout);

    return 0;
}