#include <bits/stdc++.h>
using namespace std;
using ll = long long;

// A node in the merge-tree: 32‑bit children indices, 64‑bit sum.
struct MergeNode {
    int left, right;
    ll sum;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // --- 1) File I/O setup ---
    ifstream in("huffman.in");
    ofstream out("huffman.out");
    int n;
    in >> n;

    // --- 2) Read frequencies ---
    vector<ll> freq(n);
    for(int i = 0; i < n; i++){
        in >> freq[i];
    }

    // Special case: only one symbol
    if(n == 1){
        // It must get a code of length 1, code 0.
        out << freq[0] << "\n";
        out << 1 << " " << 0 << "\n";
        return 0;
    }

    // --- 3) Prepare two queues: Q1 = leaves, Q2 = merged nodes ---
    vector<pair<ll,int>> Q1(n), Q2;
    Q2.reserve(n);

    for(int i = 0; i < n; i++){
        // leaf indices 1..n
        Q1[i] = make_pair(freq[i], i + 1);
    }
    sort(Q1.begin(), Q1.end(),
         [](const pair<ll,int>& a, const pair<ll,int>& b){
             return a.first < b.first;
         });
    int p1 = 0, p2 = 0;         // pointers into Q1 and Q2
    int nodeCnt = n;           // next new node will be ++nodeCnt
    vector<MergeNode> tree(2*n + 2);
    ll totalCost = 0;

    // initialize leaf nodes
    for(int i = 1; i <= n; i++){
        tree[i].left  = 0;
        tree[i].right = 0;
        tree[i].sum   = freq[i-1];
    }

    // helper to pick the smallest head among Q1[p1] and Q2[p2]
    auto pick_min = [&](pair<ll,int> &out){
        if(p1 < n && (p2 >= (int)Q2.size() || Q1[p1].first <= Q2[p2].first)){
            out = Q1[p1++];
        } else {
            out = Q2[p2++];
        }
    };

    // --- 4) Merge loop: n-1 merges ---
    for(int merge = 0; merge < n - 1; merge++){
        pair<ll,int> A, B;
        pick_min(A);
        pick_min(B);

        totalCost += A.first + B.first;

        // create an internal node
        ++nodeCnt;
        tree[nodeCnt].left  = A.second;
        tree[nodeCnt].right = B.second;
        tree[nodeCnt].sum   = A.first + B.first;

        // push new node into Q2
        Q2.emplace_back(tree[nodeCnt].sum, nodeCnt);
    }

    int root = nodeCnt;

    // --- 5) DFS to compute each leaf's code-length ---
    vector<int> length(n+1, 0);
    vector<pair<int,int>> stack;
    stack.reserve(2*n);
    stack.push_back(make_pair(root, 0));

    while(!stack.empty()){
        pair<int,int> top = stack.back();
        stack.pop_back();
        int u = top.first;
        int depth = top.second;
        if(u <= n){
            // it's a leaf
            length[u] = depth;
        } else {
            // push children (order doesn't matter)
            stack.push_back(make_pair(tree[u].right, depth + 1));
            stack.push_back(make_pair(tree[u].left,  depth + 1));
        }
    }

    // --- 6) Build canonical Huffman codes from lengths ---
    vector<pair<int,int>> byLen(n);
    for(int i = 1; i <= n; i++){
        byLen[i-1] = make_pair(length[i], i);
    }
    sort(byLen.begin(), byLen.end(),
         [](const pair<int,int>& a, const pair<int,int>& b){
             if(a.first != b.first) return a.first < b.first;
             return a.second < b.second;
         });

    vector<ll> code(n+1, 0);
    ll curCode = 0;
    int prevLen = byLen[0].first;
    code[ byLen[0].second ] = 0;  // first code is 0

    for(int i = 1; i < n; i++){
        int L   = byLen[i].first;
        int idx = byLen[i].second;
        curCode++;
        if(L > prevLen){
            // shift left for longer codes
            curCode <<= (L - prevLen);
            prevLen = L;
        }
        code[idx] = curCode;
    }

    // --- 7) Output results ---
    out << totalCost << "\n";
    for(int i = 1; i <= n; i++){
        out << length[i] << " " << code[i] << "\n";
    }

    return 0;
}