// Heap - O (N log N)

#include <fstream>
#include <string>
#include <algorithm>

using namespace std;

#define maxN 1000005
#define LL long long

LL H[maxN], poz[maxN], dim; // Heap
int v[maxN];
int arb[2 * maxN], dimarb, tata[2 * maxN]; // Arborele Huffman
int K, N;


void pop (int nod)
{
	int nodmin = nod;
	int st = nod * 2, dr = nod * 2 + 1;
	
	if (st <= dim && H[st] < H[nodmin]) nodmin = st;
	if (dr <= dim && H[dr] < H[nodmin]) nodmin = dr;
	
	if (nod == nodmin) return;
	
	swap (H[nodmin], H[nod]);
	swap (poz[nodmin], poz[nod]);
	
	pop (nodmin);
}


void push (int nod)
{
	if (nod == 1) return;
	if (H[nod] >= H[nod / 2]) return;
	
	swap (H[nod], H[nod / 2]);
	swap (poz[nod], poz[nod / 2]);
	
	push (nod / 2);
}


int dfs (int nod)
{
	if (nod == 2 * N - 1) return 0;
	
	++ K; 
	
	return (1 << (K - 1)) * arb[nod] + dfs (tata[nod]);
}


int main()
{
	ifstream f ("huffman.in");
	ofstream g ("huffman.out");

	f >> N;
	
	for (int i = 1; i <= N; ++ i)
	{
		f >> v[i];
		
		H[++ dim] = v[i];
		poz[dim] = i;
		push (dim);
		
		++ dimarb;
	}
	
	LL S = 0;
	
	while (dim > 1)
	{
		LL first = H[1];
		int poz1 = poz[1];
		swap (H[1], H[dim]);
		swap (poz[1], poz[dim]);
		-- dim;
		pop (1);
		
		LL sec = H[1];
		int poz2 = poz[1];
		swap (H[1], H[dim]);
		swap (poz[1], poz[dim]);
		-- dim;
		pop (1);
		
		arb[poz1] = 0;
		arb[poz2] = 1;
		tata[poz1] = ++ dimarb;
		tata[poz2] = dimarb;
		
		S += first + sec;
		H[++ dim] = first + sec;
		poz[dim] = dimarb;
	}
	

	g << S << '\n';
	
	for (int i = 1; i <= N; ++ i)
	{
		K = 0;
		g << K << " " << dfs (i) << '\n';
	}
	
	return 0;
}