#include <iostream>
#include <fstream>
#include <queue>
#define MAX_SIZE 1000002
using namespace std;
ifstream fin("huffman.in");
ofstream fout("huffman.out");
int n;
int v1[MAX_SIZE];
long long v2[MAX_SIZE];
struct nod {
    int val;
    long long length;
    nod *left, *right;
};

void df(nod *R, int l, long long s) {
    if(R->val != 0) {
        v1[R->val] = l;
        v2[R->val] = s;
    } else {
        l++;
        df(R->left, l, (s<<1));
        df(R->right, l, (s<<1) + 1);
    }
}
queue <nod*> q;
queue <nod*> v;
int main()
{
    fin>>n;
    for(int i = 1; i <= n; i++) {
        nod *x = new nod;
        fin>>x->length;
        x->val = i;
        v.push(x);
    }
    long long s = 0;
    while(!v.empty()) {
        nod *x, *y;
        if(v.front()->length > q.front()->length) {
            x = q.front();
            q.pop();
        } else {
            x = v.front();
            v.pop();
        }
        if(v.front()->length > q.front()->length || v.empty()) {
            y = q.front();
            q.pop();
        } else {
            y = v.front();
            v.pop();
        }

        long long k = x->length + y->length;
        nod *t = new nod;
        t->left = x;
        t->right = y;
        t->length = k;
        t->val = 0;
        s += k;
        q.push(t);
    }
    while(q.size() > 1) {
        nod *x = q.front();
        q.pop();
        nod *y = q.front();
        q.pop();

        long long k = x->length + y->length;
        nod *t = new nod;
        t->left = x;
        t->right = y;
        t->length = k;
        t->val = 0;
        s += k;
        q.push(t);
    }
    fout<<s<<'\n';
    df(q.front(), 0, 0);
    /*
    for(int i = 1; i <= n; i++) {
        fout<<v1[i]<<' '<<v2[i]<<'\n';
    }
    */
    fin.close();
    fout.close();
    return 0;
}