// Huffman.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

class Nod
{
private:
	// Leaves
	long long nod1, nod2;
	long long suma;

	// Internal Node
	Nod *nodInternal1, *nodInternal2;

public:
	Nod () : nod1(0), nod2(0), suma(0), nodInternal1(NULL), nodInternal2(NULL) { }
	Nod (long long nod1Nou) : nod1(nod1Nou), nod2(-1), suma(nod1Nou), nodInternal1(NULL), nodInternal2(NULL) { }
	Nod (long long nod1Nou, long long nod2Nou) : nod1(nod1Nou), nod2(nod2Nou), suma (nod1Nou + nod2Nou), nodInternal1(NULL), nodInternal2(NULL){ }
	Nod (Nod *nod1Nou, Nod *nod2Nou, long long sumaNoua) : nodInternal1(nod1Nou), nodInternal2(nod2Nou), suma(sumaNoua), nod1(-1) { }

	bool operator< (const Nod& otherNod) const
	{	return suma >= otherNod.suma;	}
	bool operator> (const Nod& otherNod) const
	{	return suma < otherNod.suma;	}
	bool operator==(const Nod& otherNod) const
	{	return nod1 == otherNod.nod1 && nod2 == otherNod.nod2;	}
	
	long long GetSuma () const
	{	return suma;	}
	long long GetNod1 () const
	{	return nod1;	}
	long long GetNod2 () const
	{	return nod2;	}

	bool AreFii() const
	{	return nodInternal1 != NULL && nodInternal2 != NULL;	}

	Nod *GetStanga () { return nodInternal1; }
	Nod *GetDreapta() { return nodInternal2; }
};

long long putere (long long baza, long long put)
{
	if (put == 0)
		return 1;
	 
	if (put % 2 == 0)
	{
		long long rezultat = putere (baza, put / 2);
		return rezultat * rezultat;
	}
	else
		return baza * putere (baza, put - 1);
}

long long toBaza(const vector<long long>& nr, long long bazaProv, long long bazaConversie)
{
	long long rezultat = 0; long long cnt = nr.size();
	for (vector<long long>::const_iterator i = nr.begin(); i != nr.end(); i++)
	{
		long long element = *i;
		rezultat += element * putere(bazaProv, --cnt);
	}
	
	return rezultat;
}


vector<long long> path;
vector<pair<long long, long long> > paths;
void Inordine (Nod *Root)
{
	if (Root == NULL)
		return;
	
	if (Root->AreFii() == false)
		paths.push_back (make_pair (path.size(), toBaza(path, 2, 10)));
	
	//printf ("Ma duc in stanga si merg pe suma: &llu \n", Root->GetSuma());
	path.push_back(0);
	Inordine(Root->GetStanga());
	path.pop_back();
	
	//printf ("Afisez date: \n");
	//printf ("Nod1: &llu,\t Suma: &llu;\n", Root->GetNod1(), Root->GetSuma(), Root->AreFii()); 		
	
	//printf ("Ma duc in dreapta si merg pe suma: &llu \n", Root->GetSuma());
	path.push_back(1);
	Inordine(Root->GetDreapta());
	path.pop_back();
}

bool cmpFunc (const pair<long long, long long>& p1, const pair<long long, long long>& p2)
{
	if (p1.first == p2.first)
		return p1.second < p2.second;
	else
		return p1.first > p2.first;
}

int main(long long argc, char* argv[])
{
	FILE *in, *out;
	in  = fopen ("huffman.in",  "r");
	out = fopen ("huffman.out", "w");

	priority_queue<Nod> myQueue;

	long long i, n; fscanf (in, "&llu", &n);
	for (i = 0; i < n; ++i)
	{
		long long x; fscanf (in, "&llu", &x);

		Nod newNode(x); 
		myQueue.push(x);
	}
	
	long long suma = 0;
	while (myQueue.size() > 1)
	{
		Nod nod1 = myQueue.top(); myQueue.pop();
		Nod nod2 = myQueue.top(); myQueue.pop();

		Nod *nod1Nou = new Nod(nod1);
		Nod *nod2Nou = new Nod(nod2);

		Nod nodNou(nod1Nou, nod2Nou, nod1.GetSuma() + nod2.GetSuma());
		myQueue.push(nodNou);

		suma += nod1.GetSuma() + nod2.GetSuma();

		nod1Nou->~Nod();
		nod2Nou->~Nod();
	}

	Nod root = myQueue.top(); myQueue.pop();
	
	fprintf (out, "&llu\n", suma);
	Inordine (&root);

	sort (paths.begin(), paths.end(), cmpFunc);
	for (vector<pair<long long, long long> >::iterator it = paths.begin(); it != paths.end(); ++it)
		fprintf (out, "&llu &llu\n", it->first, it->second);

	return 0;
}