#include<iostream>
#include<fstream>
#include<deque>
//folosim clasa deque deoarece ne permite sa accesam mai rapid fiecare element, respectiv sa stergem si sa inseram mai usor

using namespace std;

ifstream fin("huffman.in");
ofstream fout("huffman.out");

deque<int> v,inter;

// functie care alege cea mai mica valoare
int get_minimal(){
    int minval;

    if(v.empty()){
        minval=inter.front();
        inter.pop_front();
    }
    else if(inter.empty()){
        minval=v.front();
        v.pop_front();
    }
    else{
            // returnam minimul dintre valoarea intermediara si cea din vectorul obtinut din frecventele initiale
        if(c[inter.front()]<c[v.front()]){
            minval=inter.front();
            inter.pop_front();
        }
        else{
            minval=v.front();
            v.pop_front();
        }
    }
    return minval;
}

// retinem in d adancimea la care se afla fiecare nod
void dfs(int node,long long repr,int depth){
    if(l[node]==0 && r[node]==0){
        ans[node]=repr;
        d[node]=depth;
    }
    else{
        dfs(l[node],repr<<1,depth+1);
        dfs(r[node],(repr<<1)+1,depth+1);
    }
}



int main(){
    ifstream fin("huffman.in");
    ofstream fout("huffman.out");
    fin>>n;

    for(int i=1;i<=n;i++){
        fin>>c[i];
        v.push_back(i);
    }
    int cnt=n+1;
    while(v.size()+inter.size()!=1){

        int a=get_minimal();
        int b=get_minimal();

        l[cnt]=a;
        // fiul din stanga
        r[cnt]=b;
        // fiul din dreapta
        c[cnt]=c[a]+c[b];
        // suma celor 2 fii
        inter.push_back(cnt);

        cnt++;
    }

    int now=inter.front();
    dfs(now,0,0);

 //suma totala obtinuta din arbore
    long long total=0;
    for(int i=1;i<=n;i++){
        total+=c[i]*d[i];
    }


    fout<<total<<'\n';
    for(int i=1;i<=n;i++){
        fout<<d[i]<<" "<<ans[i]<<'\n';
    }
    return 0;
}