#include <fstream>
#include <queue>

using namespace std;

struct node
{
	unsigned long long val;
	int parent;
	node(unsigned long long v = 0, int p = 0) :val(v), parent(p) {};
}symbol_q[2000000];

pair<int, unsigned long long> getCode(node* nod)
{
	int lung = 0;
	unsigned long long cod = 0;
	unsigned long long pow = 1;
	while (nod->parent != 0)
	{
		++lung;
		if (nod->parent < 0)
			cod += pow;
		pow *= 2;
		nod = &symbol_q[abs(nod->parent)];

	}
	return make_pair(lung, cod);
}

int main()
{
	ifstream in("huffman.in");
	ofstream out("huffman.out");
	int nodes;
	long long freq;
	long long lg = 0;
	queue<int> internal_q;

	in >> nodes;
	for (int i = 0; i < nodes; ++i)
	{
		in >> freq;
		symbol_q[i].val=freq;
	}
	int pos = 0;
	int pos2 = nodes;
	while (pos < nodes || internal_q.size() > 1)
	{
		int min1, min2;
		if (pos == nodes)
		{
			min1 = internal_q.front();
			internal_q.pop();
			min2 = internal_q.front();
			internal_q.pop();
			lg += symbol_q[min1].val + symbol_q[min2].val;
				
		}
		else if (internal_q.empty())
		{
			min1 = pos;
			++pos;
			min2 = pos;
			++pos;
		}
		else
		{
			if (symbol_q[pos].val <= symbol_q[internal_q.front()].val)
			{
				min1 = pos;
				++pos;
			}
			else
			{
				min1 = internal_q.front();
				internal_q.pop();
				lg += symbol_q[min1].val;
			}
			if (pos < nodes && !internal_q.empty())
			{
				if (pos < nodes && symbol_q[pos].val <= symbol_q[internal_q.front()].val)
				{
					min2 = pos;
					++pos;
				}
				else
				{
					min2 = internal_q.front();
					internal_q.pop();
					lg += symbol_q[min2].val;
				}
			}
			else
			{
				if (pos == nodes)
				{
					min2 = internal_q.front();
					internal_q.pop();
					lg += symbol_q[min2].val;
				}
				else
				{
					min2 = pos;
					++pos;
				}
			}

		}

		internal_q.push(pos2);
		symbol_q[pos2].val = symbol_q[min1].val + symbol_q[min2].val;
		symbol_q[min1].parent = pos2;
		symbol_q[min2].parent = -pos2;
		++pos2;

	}
	lg += symbol_q[pos2-1].val;
	in.close();
	out << lg << "\n";
	for (int i = 0; i < nodes; ++i)
	{
		auto res = getCode(&symbol_q[i]);
		out << res.first << " " << res.second << "\n";
	}
}