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

using namespace std;

typedef struct result_node{
    long long encoding;
    int depth;
} RESULT_NODE;

typedef struct node{
    long long value;
    int index;
    struct node *left;
    struct node *right;
} NODE;

deque<NODE *> leafQ;
deque<NODE *> internalQ;

RESULT_NODE resultingCodes[1000001];
long long currentCode = 0;
long long totalSum = 0;

NODE *getMinimum(deque<NODE *> &leafQ, deque<NODE *> &internalQ){
    NODE *resultingNode;

    if (leafQ.size() > 0){
        if (internalQ.size() > 0){
            if (leafQ.front()->value < internalQ.front()->value){
                resultingNode = leafQ.front();
                leafQ.pop_front();
            } else {
                resultingNode = internalQ.front();
                internalQ.pop_front();
            }
        } else {
            resultingNode = leafQ.front();
            leafQ.pop_front();
        }
    }
    else {
        resultingNode = internalQ.front();
        internalQ.pop_front();
    }

    return resultingNode;
}

void inorder(NODE *p, int depth){
    if (p->left == NULL && p->right == NULL){
        RESULT_NODE n;
        n.encoding = currentCode;
        n.depth = depth;
        resultingCodes[p->index] = n;
    } else {
        totalSum += p->value;
        currentCode = currentCode << 1;
        inorder(p->left, depth+1);

        currentCode += 1;
        inorder(p->right, depth+1);

        currentCode = currentCode >> 1;
    }
}

int n, frequency;

int main()
{
    freopen("huffman.in", "r", stdin);

    scanf("%d", &n);

    for (int i=0; i<n; i++){
        scanf("%d", &frequency);

        NODE *p = (NODE *)malloc(sizeof(NODE));
        p->left = NULL;
        p->right = NULL;
        p->index = i;
        p->value = (long long)frequency;

        leafQ.push_back(p);
    }

    fclose(stdin);


    NODE *p1;
    NODE *p2;

    while ((leafQ.size() + internalQ.size()) > 1){
        p1 = getMinimum(leafQ, internalQ);
        p2 = getMinimum(leafQ, internalQ);

        NODE *newNode = (NODE *)malloc(sizeof(NODE));
        newNode->left = p1;
        newNode->right = p2;
        newNode->value = p1->value + p2->value;

        internalQ.push_back(newNode);
    }

    inorder(internalQ.front(), 0);

    freopen("huffman.out", "w", stdout);
    printf("%lld\n", totalSum);

    for (int i=0; i<n; i++){
        printf("%d %lld\n", resultingCodes[i].depth, resultingCodes[i].encoding);
    }

    fclose(stdout);

    return 0;
}