#include <fstream>
#include <vector>

using namespace std;

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

const int N = 2 * 1000005, M = 1000005;

int n, maxlvl, nrn, niv[N];

long long tot, val[N];

int Q1[M], Q2[M];

vector <int> L[N];

void read() {
    in >> n;

    for (int i = 1; i <= n; ++i) {
        in >> val[i];
        Q1[++ Q1[0]] = i;
    }
}

void make_trie() {
    int x, y, poz1 = 1, poz2 = 1;
    nrn = n;

    while ((Q1[0] - poz1 + 1 > 1 || Q2[0] - poz2 + 1 > 1) || (Q1[0] - poz1 + 1 == 1 && Q2[0] - poz2 + 1 == 1)) {
        if (Q1[0] == poz1 - 1) {
            x = Q2[poz2];
            ++ poz2;

            y = Q2[poz2];
            ++ poz2;
        } else if(Q2[0] == poz2 - 1) {
            x = Q1[poz1];
            ++ poz1;

            y = Q1[poz1];
            ++ poz1;
        } else {
            if (val[Q1[poz1]] > val[Q2[poz2]]) {
                x = Q2[poz2];
                ++ poz2;
            } else {
                x = Q1[poz1];
                ++ poz1;
            }

            if (Q1[0] == poz1 - 1) {
                y = Q2[poz2];
                ++ poz2;
            } else if (Q2[0] == poz2 - 1) {
                y = Q1[poz1];
                ++ poz1;
            } else {
                if (val[Q1[poz1]] > val[Q2[poz2]]) {
                    y = Q2[poz2];
                    ++ poz2;
                } else {
                    y = Q1[poz1];
                    ++ poz1;
                }
            }
        }

        ++ nrn;

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

        Q2[++ Q2[0]] = nrn;

        val[nrn] = val[x] + val[y];

        tot += val[nrn];
    }

    out << tot << '\n';
}

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

    niv[nod] = lvl;

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

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

void afis() {
    for (int i = 1; i <= n; ++ i)
        out << niv[i] << ' ' << val[i] << '\n';
}

int main() {
    read();

    make_trie();

    solve(nrn, 0, 0);

    afis();

    return 0;
}