#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 = 1e6 + 5;

int N,nrNode,stL = 1,drL,stI = 1,drI;
ll codeLength[NMax],codeValue[NMax];
int leafQueue[NMax],inQueue[NMax];

struct nodeType {
    ll val,id;
    int st,dr;
    nodeType(ll _val = 0,ll _id = 0): val(_val), id(_id), st(0), dr(0) {}
}node[2*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[++drL] = nrNode;
    }

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

    ll len = 0;
    while ((drL - stL + 1) + (drI - stI + 1) > 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;
        inQueue[++drI] = 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 (stL > drL || ( stI <= drI && node[inQueue[stI]].val < node[leafQueue[stL]].val )) {
        ret = inQueue[stI++];
    }
    else {
        ret = leafQueue[stL++];
    }

    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);
}