#include <fstream>
#include <queue>


using namespace std;

struct node
{
	char type;
	unsigned long long val;
	node *parent;
	node(char t='n', unsigned long long v = 0, node* p = nullptr) : type(t), val(v), parent(p) {};
};

pair<unsigned int, unsigned long long> getCode(node* nod)
{
	unsigned int lung = 0;
	unsigned long long cod = 0;
	int pow = 1;
	while (nod->type != 'n')
	{
		++lung;
		if (nod->type == 'r')
			cod += pow;
		pow *= 2;
		nod = nod->parent;

	}
	return make_pair(lung, cod);
}

int main()
{
	ifstream in("huffman.in");
	ofstream out("huffman.out");
	unsigned int nodes;
	unsigned int freq;
	unsigned long long lg = 0;
	node** symbol_q;
	symbol_q = new node * [1000000];
	queue <node*> internal_q;
	in >> nodes;
	for(int i=0; i<nodes; ++i)
	{
		in >> freq;
		symbol_q[i]= new node('n', freq, nullptr);
	}
	int pos = 0;
	while(pos < nodes || internal_q.size() > 1)
	{
		node *min1, *min2;
		if (pos == nodes)
		{
			min1 = internal_q.front();
			internal_q.pop();
			min2 = internal_q.front();
			internal_q.pop();
			lg += min1->val + min2->val;
		}
		else if(internal_q.empty())
		{
			min1 = symbol_q[pos];
			++pos;
			min2 = symbol_q[pos];
			++pos;
		}
		else
		{
			if (symbol_q[pos]->val <= internal_q.front()->val)
			{
				min1 = symbol_q[pos];
				++pos;
			}
			else
			{
				min1 = internal_q.front();
				internal_q.pop();
				lg += min1->val;
			}
			if (pos < nodes && !internal_q.empty())
			{
				if (pos < nodes && symbol_q[pos]->val <= internal_q.front()->val)
				{
					min2 = symbol_q[pos];
					++pos;
				}
				else
				{
					min2 = internal_q.front();
					internal_q.pop();
					lg += min2->val;
				}
			}
			else
			{
				if(pos == nodes)
				{
					min2 = internal_q.front();
					internal_q.pop();
					lg += min2->val;
				}
				else
				{
					min2 = symbol_q[pos];
					++pos;
				}
			}

		}

		internal_q.push(new node('n', min1->val + min2->val, nullptr));
		min1->type = 'l';
		min1->parent = internal_q.back();
		min2->type = 'r';
		min2->parent = internal_q.back();

	}
	lg += internal_q.front()->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";
	}
	
	//memory leak, whatever I just want this to work for now
}