#include <fstream>
#include <vector>

#include <cstdio>
using namespace std;

const int MAX_N = 1000002;
const int SIGMA = 2;

struct Node {
    int ind;
    int sons[SIGMA];
    long long val;

    Node() {
        val = ind = 0;
        for(int i = 0; i < SIGMA; ++i)
            sons[i] = 0;
    }
};

int N;
long long ans;
long long frequency[MAX_N];
pair < int, long long > sol[MAX_N];
Node v[2 * MAX_N];
vector < Node > a, b;

void DFS(Node node, long long code, int lv) {
    for(size_t i = 0; i < SIGMA; ++i)
        if(node.sons[i])
            DFS(v[node.sons[i]], code + (i << lv), lv + 1);
    if(node.ind <= N) {
        sol[node.ind] = make_pair(lv, code);
        ans += (long long) frequency[node.ind] * lv;
    }
}

Node getMin(int &p_a, int &p_b) {
    if(p_a >= a.size())
        return b[p_b++];
    else if(p_b >= b.size())
        return a[p_a++];
    else if(a[p_a].val < b[p_b].val)
        return a[p_a++];
    else
        return b[p_b++];
}

int main() {
    ifstream f("huffman.in");
    ofstream g("huffman.out");

    f >> N;
    Node temp;
    for(int i = 1; i <= N; ++i) {
        f >> frequency[i];

        temp.val = frequency[i];
        temp.ind = i;
        v[i] = temp;
        a.push_back(temp);
    }

    int p = N + 1;
    Node node, temp1, temp2;
    for(int i = 0, j = 0; i < a.size() || j < b.size() - 1; ) {
        temp1 = getMin(i, j);
        temp2 = getMin(i, j);

        node.val = temp1.val + temp2.val;
        node.ind = p;
        node.sons[0] = temp1.ind, node.sons[1] = temp2.ind;
        v[p] = node;
        ++p;

        b.push_back(node);
    }

    DFS(b[b.size() - 1], 0, 0);

    g << ans << "\n";
    for(int i = 1; i <= N; ++i)
        g << sol[i].first << " " << sol[i].second << "\n";

    f.close();
    g.close();

    return 0;
}