#include<fstream>
#define DIM 1000005
#define f first
#define s second
using namespace std;
int n, nr, p, p1, u1, i, minim1, minim2, a1, a2;
int v[DIM], c[DIM], niv[2 * DIM];
pair<int, int> ff[2 * DIM];
long long sum, sol[DIM];
ifstream fin("huffman.in");
ofstream fout("huffman.out");
void verif(int poz){
    if(minim1 > c[poz]){
        a2 = a1;
        minim2 = minim1;
        minim1 = c[poz];
        a1 = 2;
    }
    else{
        if(minim2 > c[poz]){
            a2 = 2;
            minim2 = c[poz];
        }
    }
}
void adauga(int x, int t){
    if(x == 1){
        if(t == 0){
            ff[nr].f = p;
        }
        else{
            ff[nr].s = p;
        }
        p++;
    }
    else{
        if(t == 0){
            ff[nr].f = p1 + n;
        }
        else{
            ff[nr].s = p1 + n;
        }
        p1++;
    }
}
void dfs(int nod, long long val){
    if(nod <= n){
        sol[nod] = val;
        sum += niv[nod] * v[nod];
    }
    if(ff[nod].f == 0){
        return;
    }
    int vecin;
    vecin = ff[nod].f;
    niv[vecin] = niv[nod] + 1;
    dfs(vecin, val * 2);

    vecin = ff[nod].s;
    niv[vecin] = niv[nod] + 1;
    dfs(vecin, val * 2 + 1);
}
int main(){
    fin>> n;
    for(i = 1; i <= n; i++){
        fin>> v[i];
    }
    p = p1 = 1;
    nr = n;
    for(i = 1; i < n; i++){
        minim1 = minim2 = 1000000000;
        if(p <= n){
            minim1 = v[p];
            a1 = 1;
        }
        if(p <= n - 1){
            minim2 = v[p + 1];
            a2 = 1;
        }
        if(p1 <= u1){
            verif(p1);
        }
        if(p1 <= u1 - 1){
            verif(p1 + 1);
        }
        nr++;
        u1++;
        c[u1] = minim1 + minim2;
        adauga(a1, 0);
        adauga(a2, 1);
    }
    niv[nr] = 0;
    dfs(nr, 0);
    fout<< sum <<"\n";
    for(i = 1; i <= n; i++){
        fout<< niv[i] <<" "<< sol[i] <<"\n";
    }
    return 0;
}