#include <cstring>

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

typedef long long int64;

const int MAX_N = 1000000;
const int NIL = -1;
const int BASE = 2;

int V, Tree[2 * MAX_N][BASE], Levels[2 * MAX_N];
int64 Codes[MAX_N];
int N;
int64 Frequences[MAX_N], TotalLength;

void DFS(const int x, const int64 currentCode) {
    if (x < N)
        Codes[x] = currentCode;
    for (int i = 0; i < BASE && Tree[x][i] != NIL; ++i) {
        Levels[Tree[x][i]] = Levels[x] + 1;
        DFS(Tree[x][i], currentCode * BASE + i);
    }
}

inline pair<int64, int> ExtractFront(queue< pair<int64, int> > &first, queue< pair<int64, int> > &second) {
    pair<int64, int> front;
    if (first.empty()) {
        front = second.front();
        second.pop();
    } else if (second.empty()) {
        front = first.front();
        first.pop();
    } else {
        if (first.front() < second.front()) {
            front = first.front();
            first.pop();
        } else {
            front = second.front();
            second.pop();
        }
    }
    return front;
}

void InitializeTree() {
    memset(Tree, NIL, sizeof(Tree));
    memset(Levels, -1, sizeof(Levels));
    memset(Codes, -1, sizeof(Codes));
}

void GetHuffmanCodes() {
    InitializeTree();
    queue< pair<int64, int> > terminal, internal;
    for (int i = 0; i < N; ++i)
        terminal.push(make_pair(Frequences[i], V++));
    while (int(terminal.size()) + int(internal.size()) > 1) {
        pair<int64, int> x = ExtractFront(terminal, internal);
        pair<int64, int> y = ExtractFront(terminal, internal);
        int z = V++;
        Tree[z][0] = x.second;
        Tree[z][1] = y.second;
        internal.push(make_pair(x.first + y.first, z));
    }
    Levels[V - 1] = 0;
    DFS(V - 1, 0LL);
}

void Solve() {
    GetHuffmanCodes();
    TotalLength = 0;
    for (int i = 0; i < N; ++i)
        TotalLength += Frequences[i] * Levels[i];
}

void Read() {
    ifstream cin("huffman.in");
    cin >> N;
    for (int i = 0; i < N; ++i)
        cin >> Frequences[i];
    cin.close();
}

void Print() {
    ofstream cout("huffman.out");
    cout << TotalLength << "\n";
    for (int i = 0; i < N; ++i)
        cout << Levels[i] << " " << Codes[i] << "\n";
    cout.close();
}

int main() {
    Read();
    Solve();
    Print();
    return 0;
}