#include <bits/stdc++.h>
#define ll long long

FILE *fin = freopen("huffman.in", "r", stdin);
FILE *fout = freopen("huffman.out", "w", stdout);

using namespace std;

struct CharWithFrq {
    char c;
    ll frq;
};

struct BinaryTreeNode {
    CharWithFrq *s;
    shared_ptr<BinaryTreeNode> l, r;
    ll frq_sum;
    bool operator < (const BinaryTreeNode &ot) const {
        if (frq_sum == ot.frq_sum) {
            if (s && ot.s) {
                return s->c < ot.s->c;
            }
            if (s) {
                return true;
            }
            return false;
        }
        return frq_sum < ot.frq_sum;
    }
};

struct CustomCmp
{
    bool operator()(const shared_ptr<BinaryTreeNode> lhs, const shared_ptr<BinaryTreeNode> rhs){
        return lhs->frq_sum > rhs->frq_sum;
    }
};

struct Code {
    ll value;
    int sz;
};

void assignHuffmanCodes(vector<Code>* huffman_codes, shared_ptr<BinaryTreeNode> node, const Code &code, ll &ans) {
    if (!node) {
        return ;
    }
    if (node->s) {
        // leaf node
        (*huffman_codes)[node->s->c - 1] = code;
        ans += node->s->frq * code.sz;
    } else {
        assignHuffmanCodes(huffman_codes, node->l, Code{code.value << 1, code.sz + 1}, ans);
        assignHuffmanCodes(huffman_codes, node->r,  Code{(code.value << 1) + 1, code.sz + 1}, ans);
    }
}

void getHuffmanCode(vector<CharWithFrq>* symbols, vector<Code>* huffman_codes) {
    auto cmp = [](shared_ptr<BinaryTreeNode> lhs, shared_ptr<BinaryTreeNode> rhs)
                {
                    return lhs->frq_sum > rhs->frq_sum;
                };
    priority_queue<shared_ptr<BinaryTreeNode>, vector<shared_ptr<BinaryTreeNode>>, CustomCmp> nodes;
    for (auto& s : *symbols) {
        nodes.emplace(new BinaryTreeNode{&s, nullptr, nullptr, s.frq});
    }
    while (nodes.size() > 1) {
        shared_ptr<BinaryTreeNode> l_node = nodes.top();
        nodes.pop();
        shared_ptr<BinaryTreeNode> r_node = nodes.top();
        nodes.pop();
        nodes.emplace(new BinaryTreeNode{nullptr, l_node, r_node, l_node->frq_sum + r_node->frq_sum});
    }

    ll ans = 0;
    const Code code = Code{0LL, 0};
    assignHuffmanCodes(huffman_codes, nodes.top(), code, ans);

    printf("%lld\n", ans);
}


int main()
{
    int n;
    scanf("%d", &n);
    vector<CharWithFrq> symbols;
    vector<Code> huffman_code(n, Code{0LL, 0});
    // don't use null as symbol
    for (char c = 1; c <= n; ++ c) {
        ll frq;
        scanf("%lld", &frq);
        symbols.emplace_back(CharWithFrq{c, frq});
    }

    getHuffmanCode(&symbols, &huffman_code);
    for (char c = 0; c < n; ++ c) {
        printf("%d %lld\n", huffman_code[c].sz, huffman_code[c].value);
    }
    return 0;
}