#include <iostream>
#include <fstream>
#include <stdio.h>
#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;

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

int N,nrNode,stL = 1,drL,stI = 1,drI;
ll codeValue[NMax];
int codeLength[NMax];
int leafQueue[NMax],inQueue[NMax];
char str[strMax],*p = str;

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

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

class inputReader {
    private:
    FILE *f;
    static const int strSize = 1e4;
    char buff[strSize];
    int pos;

    char getChar() {
        if (pos == strSize) {
            fread(buff,1,strSize,f);
            pos = 0;
        }

        return buff[pos++];
    }

    public:
    inputReader(const char *fileName) {
        f = fopen(fileName,"r");
        pos = strSize;
    }

    inputReader& operator >> (int& var) {
        char c;
        int sign = 1;
        while ( !isdigit(c = getChar()) ) {
            if (c == '-') {
                sign *= -1;
            }
        }
        var = c - '0';

        while ( isdigit(c = getChar()) ) {
            var = var * 10 + c - '0';
        }
        var *= sign;

        return *this;
    }

    ~inputReader() {
        fclose(f);
    }
}in("huffman.in");

int main() {
    FILE *out = fopen("huffman.out","w");

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

        int val;
        in>>val;
        node[nrNode].val = val;
        node[nrNode].st = node[nrNode].dr = 0;
        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].val = 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);

    fprintf(out,"%lli\n",len);
    for (int i=1;i <= N;++i) {
        fprintf(out,"%i %lli\n",codeLength[i],codeValue[i]);
    }

    fclose(out);
    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,int len) {
    pv(node[nodeIndex].val);pv(node[nodeIndex].id);pv(prefix);pv(len);pn;

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

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

ll getNumber() {
    ll ans = 0;

    while (!('0' <= *p && *p <= '9')) {
        ++p;
    }

    while ('0' <= *p && *p <= '9') {
        ans = ans * 10 + *p++ - '0';
    }

    return ans;
}