#include <cstdio>
#include <deque>
#include <fstream>
using namespace std;
const int NMAX = 1.e6;

struct node{
    long long weight;
    int left, right;
    node(long long _weight = 0, int _left = 0, int _right = 0): weight(_weight), left(_left), right(_right){}
};
node tree[2 * NMAX + 5];

deque <int> dql, dqi;
long long v[NMAX + 5];
int lgc[NMAX + 5], n;
long long lg;

int get_node(){
    if(dql.empty()){
        int ti = dqi.front();
        dqi.pop_front();
        return ti;
    }
    if(dqi.empty()){
        int tl = dql.front();
        dql.pop_front();
        return tl;
    }
    int tl = dql.front();
    int ti = dqi.front();
    if(tree[tl].weight <= tree[ti].weight){
        dql.pop_front();
        return tl;
    }
    else{
        dqi.pop_front();
        return ti;
    }
}

void dfs(int nod, long long val, int lvl){   
    if(nod > n){
        lg += tree[nod].weight;
        dfs(tree[nod].left, val << 1, lvl + 1);
        dfs(tree[nod].right, (val << 1)^1, lvl + 1);
    }
    else{
        v[nod] = val;
        lgc[nod] = lvl;
    }
}

int main(){
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    int i, free;
    long long w;
    f >> n;
    for(i = 1; i <= n; i ++){
        f >> w;
        tree[i].weight = w;
        dql.push_back(i);
    }
    free = n;
    while(dql.size() + dqi.size() >= 2){
        ++ free;
        tree[free].left = get_node();
        tree[free].right = get_node();
        tree[free].weight = tree[tree[free].left].weight + tree[tree[free].right].weight;
        dqi.push_back(free);
    }
    dfs(free, 0, 0);
    g << lg;
    for(i = 1; i <= n; i ++)
        g << lgc[i] << " " << v[i];
    return 0;
}