#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;

const char iname[] = "huffman.in";
const char oname[] = "huffman.out";

typedef long long i64;

class huffman_node {

  private:
    i64 frequency;
    int index;
    huffman_node *left_child, *right_child;

  public:

    huffman_node(int freq, int idx) : frequency(freq), index(idx),
        left_child(NULL), right_child(NULL) {}

    huffman_node(int freq, int idx, huffman_node* lc, huffman_node *rc) :
        frequency(freq), index(idx), left_child(lc), right_child(rc) {}

    i64 getFrequency() const {
        return this->frequency;
    }

    huffman_node* getLeftChild() const {
        return this->left_child;
    }

    huffman_node* getRightChild() const {
        return this->right_child;
    }

    int getIndex() const {
        return index;
    }
};

bool operator < (const pair <huffman_node*, int*>& a, const pair <huffman_node*, int*>& b) {
    return a.first->getFrequency() < b.first->getFrequency();
}

vector <huffman_node*> v, q;

vector <i64> b;    vector <int> lg;

void DF(huffman_node* node, i64 code, int length) {
    if (!node->getLeftChild() && !node->getRightChild()) {
        b[node->getIndex()]  = code;
        lg[node->getIndex()] = length;
        assert(1 <= length && length <= 18);
    }
    if (node->getLeftChild())
        DF(node->getLeftChild(), code * 2, length + 1);
    if (node->getRightChild())
        DF(node->getRightChild(), code * 2 + 1, length + 1);
}

int main(void) {
    ifstream in(iname);
    int n;

    assert(in >> n);
    assert(1 <= n && n <= 1000000);
    for (int i = 0; i < n; ++ i) {
        int fr;
        assert(in >> fr);
        assert(1 <= fr && fr <= 100000000);
        v.push_back(new huffman_node(fr, i));
    }
    in.close();

    b.resize(n), lg.resize(n);
    int v_idx, q_idx;
    for (v_idx = q_idx = 0; q.size() < n - 1; ) {
        vector < pair <huffman_node*, int*> > s;
        for (int i = v_idx; i < min(v_idx + 2, (int) v.size()); ++ i)
            s.push_back(make_pair(v[i], &v_idx));
        for (int i = q_idx; i < min(q_idx + 2, (int) q.size()); ++ i)
            s.push_back(make_pair(q[i], &q_idx));
        sort(s.begin(), s.end());
        q.push_back(new huffman_node(s[0].first->getFrequency() + s[1].first->getFrequency(), -1, s[0].first, s[1].first));
        (*s[0].second)++;
        (*s[1].second)++;
    }

    assert(q.size() == v.size() - 1);
    i64 res = 0;
    for (int i = 0; i < (int) q.size(); ++ i)
        res += q[i]->getFrequency();
    assert(1 <= res && res <= 1LL << 18LL);
    DF(q[q.size() - 1], 0, 0);

    ofstream out(oname);
    out << res << "\n";
    for (int i = 0; i < v.size(); ++ i)
        out << b[i] << " " << lg[i] << "\n";
    out.close();

    return 0;
}