// (c) Claudiu Mihail
// trimisa de mine doar pentru a testa timpii

#include <fstream>
#include <iostream>
#include <cstdlib>
#include <queue>

using namespace std;

typedef unsigned short uint16;
typedef unsigned long long uint64;
typedef unsigned long uint32;

#define MAXN 1000100
#define LEFT 0
#define RIGHT 1

struct Node
{
	uint64 val;
	long child[2];
};

struct Info
{
	uint64 val;
	long index;
};

template<typename T>
class CQueue
{
public:
	CQueue(const size_t cap) :
		current(0),
		capacity(cap),
		curSize(0)
	{
		Q = (T*)malloc((cap+1)*sizeof(T));
	}
	
	T front() const
	{
		return Q[current];
	}
	
	void push(const T& elem)
	{
		const size_t pos = (current+curSize) % capacity;
		curSize++;
		Q[pos] = elem;
	}
	
	void pop()
	{
		if (curSize != 0)
		{
			curSize--;
			current++;
			current %= capacity;
		}
	}
	
	bool empty() const
	{
		return (curSize == 0);
	}
	
	size_t size()
	{
		return curSize;
	}
	
	void clear()
	{
		current = 0;
		curSize = 0;
	}
	
	~CQueue()
	{
		free(Q);
	}

private:
	T* Q;
	size_t current;
	size_t capacity;
	size_t curSize;
};

Node huffmanTree[2*MAXN+1];
CQueue<long> Q1(MAXN);
CQueue<long> Q2(MAXN);

inline int extractmin()
{
	int minim;
	if (Q2.empty())
	{
		minim=Q1.front();
		Q1.pop();
		return minim;
	}
	if (Q1.empty())
	{
		minim=Q2.front();
		Q2.pop();
		return minim;
	}
	if (huffmanTree[Q2.front()].val < huffmanTree[Q1.front()].val)
	{
		minim=Q2.front();
		Q2.pop();
		return minim;
	}

	minim=Q1.front();
	Q1.pop();
	return minim;
}


int BuildHuffManTree(const long n, uint64& sum)
{
	sum = 0;
	int a,b;

	for(int i=1;i<n;++i)
	{
		a=extractmin();
		b=extractmin();
		//cout << a << " " << b << endl;
		huffmanTree[n+i].val = huffmanTree[a].val + huffmanTree[b].val;
		huffmanTree[n+i].child[0] = a;
		huffmanTree[n+i].child[1] = b;
		Q2.push(n+i);
		
		//cout << sum << endl << endl;
		
		sum += huffmanTree[n+i].val;
	}

	return extractmin();
}

uint32 lg[MAXN];
uint64 values[MAXN];

void GetHuffmanCodes(const uint32 index, const uint16 niv, const uint64 val)
{
	if (huffmanTree[index].child[0])
	{
		GetHuffmanCodes(huffmanTree[index].child[0], niv+1, val<<1);
		GetHuffmanCodes(huffmanTree[index].child[1], niv+1, (val<<1)+1);
	}
	else
	{
		//cout << "Index = " << index-1 << endl;
		lg[index-1] = niv;
		values[index-1] = val;
		//fout << niv << " " << val << "\n";
	}
}

int main()
{
	long n;
	uint64 sum = 0;
	fstream fin("huffman.in", fstream::in);
	fstream fout("huffman.out", fstream::out);
	
	fin >> n;
	//cout << n << endl;
	
	for (long i=1; i<=n; ++i)
	{
		uint32 x;
		fin >> x;
		huffmanTree[i].val = x; 
		Q1.push(i);
	}
	
	/*for (int i=0; i<n; ++i)
	{
		cout << huffmanTree[i].val << " ";
	}*/
	
	//cout << endl;
	
	const uint32 rootIndex = BuildHuffManTree(n, sum);
	
	fout << sum << "\n";
	GetHuffmanCodes(rootIndex, 0, 0);
	
	for (long i=0; i<n; ++i)
	{
		fout << lg[i] << " " << values[i] << "\n";
	}
	
	fin.close();
	fout.close();
	return 0;
}