#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];

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];

struct comp {
    bool operator () (const int& idx1,const int& idx2) {
        return node[idx1].val > node[idx2].val;
    }
};

void dfs(int,ll,ll);

int main() {
    priority_queue<int,vector<int>,comp> pq;

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

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

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

    ll len = 0;
    while (pq.size() > 1) {
        int idx1 = pq.top(); pq.pop();
        int idx2 = pq.top(); pq.pop();

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

        len += node[nrNode].val;
        pq.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;
}

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