//Huffman e un algoritm ce minimizeaza suma(val[i] * h[i])
//unde h[] = adincimea in arbore, val[] = valoarea nodului
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 1000010
#define LL long long

int N, nrnod;
LL sol;
LL B[2*maxn], lg[2*maxn];

struct vector {
    int st, dr;
    LL val;
} A[2 * maxn];

int Q1[2 * maxn], Q2[2 * maxn];
int L1 = 1, R1 = 0, L2 = 1, R2 = 0;

void solve() {
    int i, x[3], ok = 1;

    while(ok) {
         //aleg cele mai mici 2 elemente
         for(i=1; i<=2; i++) {
              if(L1 <= R1 && L2 <= R2) {
                   if(A[ Q1[L1] ].val < A[ Q2[L2] ].val) {
                        x[i] = Q1[L1]; L1 ++;
                   }
                   else {
                        x[i] = Q2[L2]; L2 ++;
                   }
              }
              else if(L1 <= R1 && L2 > R2) {
                   x[i] = Q1[L1]; L1 ++;
              }
              else if(L1 > R1 && L2 <= R2) {
                   x[i] = Q2[L2]; L2 ++;
              }
         }

         nrnod ++;
         A[nrnod].val = A[ x[1] ].val + A[ x[2] ].val;
         A[nrnod].st = x[1], A[nrnod].dr = x[2];

         if(L1 > R1) {
              R1 ++;
              Q1[R1] = nrnod;
         }
         else {
              R2 ++;
              Q2[R2] = nrnod;
         }

         if(L1 - R1 == 0 && L2 > R2) { ok = 0; }
         if(L1 > R1 && L2 - R2 == 0) { ok = 0; }
    }
}

void DFS(int nod, int lvl, LL cod) {
    if(A[nod].st || A[nod].dr) {
         sol += A[nod].val;
    }

    lg[nod] = lvl; B[nod] = cod;

    if(A[nod].st) {
         DFS(A[nod].st, lvl + 1, 2 * cod); //pun 0 pe muchie
    }
    if(A[nod].dr) {
         DFS(A[nod].dr, lvl + 1, 2 * cod + 1); //pun 1 pe muchie
    }
}

int main() {
    FILE *f1=fopen("huffman.in", "r"), *f2=fopen("huffman.out", "w");
    int i, j, p;

    fscanf(f1, "%d\n", &N);
    for(i=1; i<=N; i++) {
         fscanf(f1, "%d\n", &A[i].val);

         A[i].st = A[i].dr = 0;

         R1 ++;
         Q1[R1] = i;
    }

    nrnod = N;

    solve();
    DFS(nrnod, 0, 0);

    fprintf(f2, "%lld\n", sol);
    for(i=1; i<=N; i++) {
         fprintf(f2, "%lld %lld\n", lg[i], B[i]);
    }

    fclose(f1); fclose(f2);
    return 0;
}