#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int N = 2 * 1000005;

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

long long tot,  val[N];

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

vector <int> L[N];

void read() {
    int x;

    in >> n;

    for (int i = 1; i <= n; ++i) {
        in >> x;
        Q1.push(make_pair(i, x));
    }
}

void make_trie() {
    pair <int, long long> 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, (long long)x.second + y.second));

        tot += (long long)x.second + y.second;
    }

    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, lvl + 1);
    solve(L[nod][1], valc + ((long long)1 << (maxlvl - 1 - lvl)), lvl + 1);
}

void compute_maxlvl(int nod, int lvl) {
    if (lvl > maxlvl)
        maxlvl = lvl;

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

    compute_maxlvl(L[nod][0], lvl + 1);
    compute_maxlvl(L[nod][1], lvl + 1);
}

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

int main() {
    read();

    make_trie();

    compute_maxlvl(nrn, 0);

    solve(nrn, 0, 0);

    afis();

    return 0;
}