#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int N = 4 * 1000000;

int n, nrn, tot, val[N], niv[N];

queue <pair <int, int> > Q1, Q2;

vector <int> L[N];

void read() {
    int x;

    scanf("%d", &n);

    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        Q1.push(make_pair(i, x));
    }
}

void make_trie() {
    pair <int, int> x, y;
    nrn = n;

    while ((Q1.size() > 1 || Q2.size() > 1) || (Q1.size() == 1 && Q2.size() == 1)) {
        if (Q1.empty()) {
            x = Q2.front();
            Q2.pop();

            y = Q2.front();
            Q2.pop();
        } else if(Q2.empty()) {
            x = Q1.front();
            Q1.pop();

            y = Q1.front();
            Q1.pop();
        } else {
            if (Q1.front().second > Q2.front().second) {
                x = Q2.front();
                Q2.pop();
            } else {
                x = Q1.front();
                Q1.pop();
            }

            if (Q1.empty()) {
                y = Q2.front();
                Q2.pop();
            } else if (Q2.empty()) {
                y = Q1.front();
                Q1.pop();
            } else {
                if (Q1.front().second > Q2.front().second) {
                    y = Q2.front();
                    Q2.pop();
                } else {
                    y = Q1.front();
                    Q1.pop();
                }
            }
        }

        ++ nrn;

        L[nrn].push_back(x.first);
        L[nrn].push_back(y.first);

        Q2.push(make_pair(nrn, x.second + y.second));

        tot += x.second + y.second;
    }

    printf("%d\n", tot);
}

void solve(int nod, int p2, int valc, int lvl) {
    val[nod] = valc;

    niv[nod] = lvl;

    if (L[nod].empty())
        return;

    solve(L[nod][0], p2*2, valc, lvl + 1);
    solve(L[nod][1], p2*2, valc + p2, lvl + 1);
}

void afis() {
    for (int i = 1; i <= n; ++ i)
        printf("%d %d\n", niv[i], val[i]);
}

int main() {
    freopen("huffman.in", "r", stdin);
    freopen("huffman.out", "w", stdout);

    read();

    make_trie();

    solve(nrn, 1, 0, 0);

    afis();

    return 0;
}