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

struct nod {
    int weight;
    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);
        }
    }
}

nod *select(queue<nod*> &q1, queue<nod*> &q2)
{
    nod *rez;

    if (q1.size() == 0) {
        rez = q2.front();
        q2.pop();
    }
    else if (q2.size() == 0) {
        rez = q1.front();
        q1.pop();
    }
    else if (q1.front()->weight < q2.front()->weight) {
        rez = q1.front();
        q1.pop();
    }
    else {
        rez = q2.front();
        q2.pop();
    }

    return rez;
}

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;
    queue<nod*> before, after;

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

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

    while (before.size() > 0 || after.size() > 1) {
        nod *n1 = select(before, after);
        nod *n2 = select(before, after);

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

        after.push(nou);
    }

    nod *root = after.front();

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

    fout << total << "\n";

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

    return 0;
}