#include<cstdio>
#include<string>
#include<deque>

using namespace std;

#ifdef HOME
const string inputFile = "input.txt";
const string outputFile = "output.txt";
#else
const string problemName = "huffman";
const string inputFile = problemName + ".in";
const string outputFile = problemName + ".out";
#endif

typedef pair<int, int> PII;
typedef long long int lld;
const lld LINF = (1LL << 60);
const int NMAX = 1000000 + 5;

int N, M;
deque<int> A, B;
lld P[2 * NMAX];
PII S[2 * NMAX];
lld T;
lld C[NMAX];
int L[NMAX];

int get() {
    int a, b;

    if(A.empty()) a = 0;
    else a = A.front();

    if(B.empty()) b = 0;
    else b = B.front();

    if(P[a] < P[b]) {
        A.pop_front();
        return a;
    }

    B.pop_front();
    return b;
}

void dfs(int x, int len, lld val) {
    if(x <= N) {
        C[x] = val;
        L[x] = len;
        T += P[x] * 1LL * len;
        return;
    }

    dfs(S[x].first, len + 1, 2 * val);
    dfs(S[x].second, len + 1, 2 * val + 1);
}

int main() {
    int i, x, y;

    freopen(inputFile.c_str(), "r", stdin);
    freopen(outputFile.c_str(), "w", stdout);

    scanf("%d", &N);

    P[0] = LINF;

    for(i = 1; i <= N; i++) {
        scanf("%d", &P[i]);
        A.push_back(i);
    }

    M = N;

    for(i = 1; i <= N - 1; i++) {
        x = get();
        y = get();

        S[++M] = make_pair(x, y);
        P[M] = P[x] + P[y];

        B.push_back(M);
    }

    dfs(M, 0, 0);

    printf("%lld\n", T);

    for(i = 1; i <= N; i++)
        printf("%d %lld\n", L[i], C[i]);

    return 0;
}