#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 = 5e4 + 5;
const int mod = 666013;

int N;
ll codeLength[NMax],codeValue[NMax];

struct nodeType {
    ll val,id;
    nodeType *st,*dr;
    nodeType(ll _val = 0,ll _id = 0): val(_val), id(_id), st(0), dr(0) {}
};

struct comp {
    bool operator () (const nodeType& a,const nodeType& b) {
        return a.val > b.val;
    }
};

void dfs(nodeType*,ll,ll);

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

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

        nodeType node(val,i);
        pq.push(node);
    }

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

    ll len = 0;
    while (pq.size() > 1) {
        auto node1 = pq.top(); pq.pop();
        auto node2 = pq.top(); pq.pop();

        nodeType dad = nodeType(node1.val + node2.val);
        dad.st = new nodeType();
        *dad.st = node1;
        dad.dr = new nodeType();
        *dad.dr = node2;

        len += dad.val;
        pq.push(dad);
        pv(dad.val);pv(dad.id);pn;
    }
    pn;

    nodeType root = pq.top();
    pq.pop();

    dfs(&root,0,0);

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

    return 0;
}

void dfs(nodeType *node,ll prefix,ll len) {
    pv(node->val);pv(node->id);pv(prefix);pv(len);pn;

    if (node->st == nullptr) {
        codeValue[node->id] = prefix;
        codeLength[node->id] = len;
        return;
    }

    dfs(node->st, (prefix<<1) + 0, len+1);
    dfs(node->dr, (prefix<<1) + 1, len+1);
}