#include <iostream>
#include <fstream>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <iomanip>

#if 0
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

using namespace std;
ifstream in("huffman.in");
ofstream out("huffman.out");

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
const int NMax = 2e6 + 5;

int N,nrNode;
ll codeLength[NMax],codeValue[NMax];
queue<int> leafQueue,intQueue;

struct nodeType {
    ll val,id;
    int st,dr;
    nodeType(ll _val = 0,ll _id = 0): val(_val), id(_id), st(0), dr(0) {}
}node[NMax];

int popMin();
void dfs(int,ll,ll);

int main() {

    in>>N;
    for (int i=1;i <= N;++i) {
        ll val;
        in>>val;

        node[++nrNode] = nodeType(val,i);
        leafQueue.push(nrNode);
    }

    //cout<<pq.top().val;

    ll len = 0;
    while (intQueue.size() + leafQueue.size() > 1) {
        int idx1 = popMin();
        int idx2 = popMin();

        node[++nrNode] = nodeType(node[idx1].val + node[idx2].val);
        node[nrNode].st = idx1;
        node[nrNode].dr = idx2;

        len += node[nrNode].val;
        intQueue.push(nrNode);

        pv(nrNode);pv(node[nrNode].val);pv(node[nrNode].id);pn;
    }
    pn;

    dfs(nrNode,0,0);

    out<<len<<'\n';
    for (int i=1;i <= N;++i) {
        out<<codeLength[i]<<' '<<codeValue[i]<<'\n';
    }

    return 0;
}

int popMin() {
    int ret;

    if (leafQueue.empty() || ( intQueue.size() && node[intQueue.front()].val < node[leafQueue.front()].val )) {
        ret = intQueue.front();
        intQueue.pop();
    }
    else {
        ret = leafQueue.front();
        leafQueue.pop();
    }

    return ret;
}

void dfs(int nodeIndex,ll prefix,ll len) {
    pv(node[nodeIndex].val);pv(node[nodeIndex].id);pv(prefix);pv(len);pn;

    if (node[nodeIndex].st == 0) {
        codeValue[node[nodeIndex].id] = prefix;
        codeLength[node[nodeIndex].id] = len;
        return;
    }

    dfs(node[nodeIndex].st, (prefix<<1) + 0, len+1);
    dfs(node[nodeIndex].dr, (prefix<<1) + 1, len+1);
}