#include<fstream>
#include<queue>

using namespace std;

ifstream fin("huffman.in");
ofstream fout("huffman.out");

typedef int64_t var;

#define MAXN 2000005
int PARENT[MAXN];
var V[MAXN];
var BIT[MAXN];
int D[MAXN];
bool COMP[MAXN];


struct Node {
    int n;
    var c;
    Node(int a, var b) {
        n = a;
        c = b;
    }
    const bool operator<(const Node &n) const {
        return c < n.c;
    }
};

queue<Node> Q1, Q2;

Node extract_min() {
    if(Q1.empty()) {
        Node rez = Q2.front();
        Q2.pop();
        return rez;
    }
    if(Q2.empty()) {
        Node rez = Q1.front();
        Q1.pop();
        return rez;
    }
    if(Q2.front() < Q1.front()) {
        Node rez = Q2.front();
        Q2.pop();
        return rez;
    } else {
        Node rez = Q1.front();
        Q1.pop();
        return rez;
    }
}



int main() {

    var n, v;

    fin>>n;
    for(var i=1; i<=n; i++) {
        fin>>V[i];
        Q1.push(Node(i, V[i]));
    }

    while(Q1.size() + Q2.size() > 1) {
        auto node1 = extract_min();
        auto node2 = extract_min();

        PARENT[node1.n] = PARENT[node2.n] = ++n;
        BIT[node1.n] = 0;
        BIT[node2.n] = 1;
        Q2.push(Node(n, node1.c + node2.c));
    }

    var sum = 0;
    //BIT[n] = 0;
    for(var i=n-1; i>=1; i--) {
        BIT[i] |= (BIT[PARENT[i]] << 1);
        D[i] = D[PARENT[i]] + 1;
    }

    COMP[n] = 1;
    fin.seekg(ios_base::beg);
    fin>>n;


    for(var i=1; i<=n; i++) {
        sum += D[i]*V[i];
    }

    fout<<sum<<'\n';


    for(var i=1; i<=n; i++) {
        fout<<D[i]<<" "<<BIT[i]<<'\n';
    }

    return 0;
}