#include <fstream>
#include <list>
#include <tuple>
#include <inttypes.h>

using namespace std;

typedef unsigned long long ull;

// intoarce indexul nodului cu frecventa minima, si il scoate din coada
// din care facea parte; cozile sunt retinute ca niste capete de intervale;
// prima coada e vida daca indexul primului nod e mai mare decat n - 1,
// iar a doua daca indexul primului nod al ei e >= 2n - 1 sau <= n - 1;
// nodurile sunt indexate de la 0 la 2n - 2:
// de la 0 la n - 1 sunt frunzele (citite din fisier) (prima coada)
// si de la n la 2n - 2 noduri interne (adaugate si scoase pe parcurs)
// (a doua coada)
int pollMin(ull *frequencies, size_t &leafFqsFrontIdx,
				size_t &internNodesFrontIdx, size_t &internNodesBackIdx,
				size_t n) {
	if (leafFqsFrontIdx >= n && internNodesFrontIdx >= (n << 1) - 1)
		return -1;

	size_t nodeIdx;

	if (internNodesFrontIdx > internNodesBackIdx) {
		// nu sunt noduri interne in coada a 2-a
		nodeIdx = leafFqsFrontIdx;
		++leafFqsFrontIdx;
		return nodeIdx;
	} else if (leafFqsFrontIdx >= n) {
		// nu mai sunt frunze in coada din prima jumatate
		nodeIdx = internNodesFrontIdx;
		++internNodesFrontIdx;
		return nodeIdx;
	} else {
		if (frequencies[leafFqsFrontIdx] <= frequencies[internNodesFrontIdx]) {
			nodeIdx = leafFqsFrontIdx;
			++leafFqsFrontIdx;
		} else {
			nodeIdx = internNodesFrontIdx;
			++internNodesFrontIdx;
		}
		return nodeIdx;
	}
}

void huffman(ifstream &in, ofstream &out) {
	size_t n;
	in >> n;

	// in total, vor fi 2n - 1 noduri in arbore (dar sunt indexate de la 0);
	// pentru fiecare nod, retin indecsii fiilor;
	// frunzele au fiii -1
	size_t totalNodes = (n << 1) - 1;
	ull *frequencies = new ull[totalNodes];
	int *left = new int[totalNodes];
	int *right = new int[totalNodes];

	for (size_t i = 0; i < n; i++) {
		in >> frequencies[i];
		left[i] = right[i] = -1;
	}

	// coada cu frunzele are initial nodurile de la 0 la n - 1 inclusiv
	size_t leafFqsFrontIdx = 0;
	// iar cea cu nodurile interne formate ulterior e intial vida,
	// dar capetele ei vor lua valori in intervalul [n, 2n - 2]
	size_t internNodesFrontIdx = n;
	size_t internNodesBackIdx = n - 1;

	ull totalBitsCount = 0;

	while (leafFqsFrontIdx <= n - 1 || internNodesFrontIdx <= totalNodes - 1) {
		auto node1 = pollMin(frequencies, leafFqsFrontIdx, internNodesFrontIdx,
							internNodesBackIdx, n);
		auto node2 = pollMin(frequencies, leafFqsFrontIdx, internNodesFrontIdx,
							internNodesBackIdx, n);
		if (node2 == -1)
			break;

		++internNodesBackIdx;
		frequencies[internNodesBackIdx] = frequencies[node1]
						+ frequencies[node2];
		totalBitsCount += frequencies[internNodesBackIdx];
		left[internNodesBackIdx] = node1;
		right[internNodesBackIdx] = node2;
	}
	out << totalBitsCount << '\n';

	auto root = totalNodes - 1;
	list<tuple<size_t, uint64_t, size_t>> dfsStack;
	dfsStack.push_front({root, 0, 0});

	uint64_t *compression = new uint64_t[n];
	size_t *heights = new size_t[n];

	while (!dfsStack.empty()) {
		auto data = dfsStack.front();
		auto &node = get<0>(data);
		auto &code = get<1>(data);
		auto &height = get<2>(data);
		dfsStack.pop_front();

		if (right[node] != -1)
			dfsStack.push_front({right[node], (code << 1) | 1, height + 1});
		if (left[node] != -1)
			dfsStack.push_front({left[node], code << 1, height + 1});

		if (left[node] == -1 && right[node] == -1) {
			heights[node] = height;
			compression[node] = code;
		}
	}
	for (size_t i = 0; i < n; i++)
		out << heights[i] << ' ' << compression[i] << '\n';

	delete[] frequencies;
	delete[] left;
	delete[] right;
	delete[] compression;
	delete[] heights;
}

int main(void) {
	ifstream in("huffman.in");
	ofstream out("huffman.out");
	huffman(in, out);
	in.close();
	out.close();
	return 0;
}