#include <stdio.h>
#include <limits>
#include <fstream>
#include <cstdio>

#define int64 long long int
#define arb node*
#define MAXX 100000001

using namespace std;

typedef struct node {
    int frecv;
    arb left;
    arb right; 
    int poz;       
} node;

arb A[1000001];
arb Init[1000001];
int InitPS, InitPF, APS, APF;

int n;
int64 S;
int V_h[1000001];
int64 V_val[1000001];
ofstream out("huffman.out", ios::binary);

char rez[12000001];
char* rezP = rez;

int get_nr() {
     int tmp = 0;
     
     int i = 0;
     while (rezP[i] < '0' || rezP[i] > '9') {
           i++;      
     } 
     rezP += i;
     
     for (i = 0; rezP[i] >= '0' && rezP[i] <= '9'; i++) {
         tmp = tmp * 10 + (rezP[i] - '0');
     } 
     rezP += i;
     return tmp;     
}

void read_() {
     FILE* in = fopen("huffman.in", "r");
     fseek(in, 0, SEEK_END);
     int64 in_size = ftell(in);
     fseek(in, 0, SEEK_SET);
     fread(rez, 1, in_size, in);
     
     n = get_nr();
          
     for (int i = 0; i < n; i++) {
         int x = get_nr();
         
         arb El = new node();
         El->frecv = x;     
         El->poz = i;
         Init[InitPF++] = El;
     } 
     fclose(in);
}

void solve_() {
     arb El = new node();
     El->frecv = numeric_limits<int>::max();
     Init[InitPF++] = El;
     
     node *El1, *El2, *Fin;
     for (int i = 1; i < n; i++) { 
         if (APF- APS == 0 || ((A[APS]->frecv) > (Init[InitPS])->frecv)) {
             El1 = Init[InitPS++];
         }
         else  {
             El1 = A[APS++];
         } 
         
         if (APF - APS == 0 || ((A[APS]->frecv) > (Init[InitPS])->frecv)) {
             El2 = Init[InitPS++];     
         }
         else  {
             El2 =A[APS++];    
         } 
         
         Fin = new node();
         Fin->frecv = El1->frecv + El2->frecv;
         if (Fin->frecv > MAXX) {
             Fin->frecv = MAXX;               
         }
         Fin->left = El1;
         Fin->right = El2; 
         
         A[APF++] = Fin;  
     }
}

int64 dfs_(arb H, int h, int64 val) { 
     int64 S1 = 0, S2 = 0;       
     if (H->left != NULL) {
         S1 = dfs_(H->left, h + 1, val << 1);
         S += S1;
     }
     if (H->right != NULL) {
         S2 = dfs_(H->right, h + 1, (val << 1) + 1);
         S += S2;
     }   
     if (H->left == NULL && H->right == NULL) { 
         V_h[H->poz] = h;
         V_val[H->poz] = val;
         return ((int64)H->frecv);      
     }
     return (S1 + S2);
}

void print_nr_space(int64 nr){
    if (nr == 0) {
        rezP[0] = '0';
        rezP[1] = ' ';    
        rezP += 2;
    }  
    else {
        int crt = 0;
        char cuv[20];
        while (nr != 0) {
             cuv[crt++] = nr % 10;
             nr /= 10;     
        } 
        for (int i = crt - 1; i >= 0; i--) {
             rezP[crt - 1 - i] = cuv[i] + '0';
        }   
        rezP[crt] = ' ';    
        rezP += (crt + 1); 
    }
}


void print_nr_newL(int64 nr){
    if (nr == 0) {
        rezP[0] = '0';
        rezP[1] = '\n';     
        rezP += 2;
    }  
    else {
        int crt = 0;
        char cuv[20];
        while (nr != 0) {
             cuv[crt++] = nr % 10;
             nr /= 10;     
        } 
        for (int i = crt - 1; i >= 0; i--) {
             rezP[crt - 1 - i] = cuv[i] + '0';
        }   
        rezP[crt] = '\n';   
        rezP += (crt + 1); 
    }
}

void print_() {
    rezP = rez;     
    print_nr_newL(S);
    for (int i = 0; i < n; i++) {
        print_nr_space(V_h[i]);
        print_nr_newL(V_val[i]);
    }    
    out.write(rez,rezP - rez);  
}
    
int main() {
    //freopen("huffman.in", "r", stdin);
    //freopen("huffman.out", "w", stdout);
    
    read_();  
    solve_();
    dfs_(A[APS], 0, 0);
    print_();    
    out.close();
    return 0;
}