#include <fstream>
#include <iostream>
#include <vector>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

struct nod {
    int weight;
    int symbol;
    nod *left;
    nod *right;
    int code_length;
    long long code_value;
};


class MyComparison
{
    public:
        bool operator() (nod *const &lhs, nod *const &rhs) const
        {
            return lhs->weight > rhs->weight;
        }
};


long long dfs(nod *n, int depth, long long cod) {
    if (n == nullptr)
        return 0;
    else {
        if (n->left == nullptr) {
            n->code_length = depth;
            n->code_value = cod;
            return (long long) depth * n->weight;
        }
        else {
            return dfs(n->left, depth+1, cod << 1)
                + dfs(n->right, depth+1, (cod << 1) + 1);
        }
    }
}

int main()
{
    ifstream fin("huffman.in");
    ofstream fout("huffman.out");

    int n;
    fin >> n;

    vector<nod*> noduri(n);

    priority_queue<nod*, deque<nod*>, MyComparison> pq;

    for (int i = 0; i < n; ++i) {
        nod *a = new nod;
        a->symbol = i;
        a->left = a->right = nullptr;
        fin >> a->weight;

        noduri[i] = a;
        pq.push(a);
    }

    while (pq.size() > 1) {
        nod *n1 = pq.top();
        pq.pop();
        nod *n2 = pq.top();
        pq.pop();

        nod *nou = new nod;
        nou->symbol = -1;
        nou->weight = n1->weight + n2->weight;
        nou->left = n1;
        nou->right = n2;

        pq.push(nou);
    }

    nod *root = pq.top();

    long long total = dfs(root, 0, 0);

    fout << total << "\n";

    for (nod *a : noduri) {
        fout << a->code_length << " " << a->code_value << "\n";
    }

    return 0;
}