// FMI - Grupa 135 - Semigrupa 2 - Hareza Andrei
// Include
#include <fstream>
#include <queue>
using namespace std;

// Definitii
#define ll long long

// Constante
const int sz = 1000001;

struct treeNode
{
	ll value;
	int leftSon, rightSon;
	treeNode()
	{
		value = 0;
		leftSon = rightSon = 0;
	}
};

struct symbol
{
	int times;
	int posInTree;
	symbol()
	{
		times = 0;
		posInTree = 0;
	}
	symbol(int newTimes, int newPosInTree)
	{
		times = newTimes;
		posInTree = newPosInTree;
	}
	
	bool operator< (symbol x) const
	{
		return times < x.times;
	}
};

// Functii
void dfs(int node, ll currentCode=0, int codeLen=0);

// Variabile
ifstream in("huffman.in");
ofstream out("huffman.out");

int num;
treeNode tree[sz*2];

queue<symbol> firstQueue;
queue<symbol> secondQueue;

ll sum;

// Main
int main()
{
	in >> num;
	for(int i=1 ; i<=num ; ++i)
	{
		in >> tree[i].value;
		firstQueue.push(symbol(tree[i].value, i));
	}
	
	int current = num;
	while(firstQueue.size() + secondQueue.size() > 1)
	{
		symbol son1, son2;
		if(firstQueue.empty())
		{
			son1 = secondQueue.front();
			secondQueue.pop();
		}
		else if(secondQueue.empty())
		{
			son1 = firstQueue.front();
			firstQueue.pop();
		}
		else
		{
			if(firstQueue.front().times < secondQueue.front().times)
			{
				son1 = firstQueue.front();
				firstQueue.pop();
			}
			else
			{
				son1 = secondQueue.front();
				secondQueue.pop();
			}	
		}
		
		if(firstQueue.empty())
		{
			son2 = secondQueue.front();
			secondQueue.pop();
		}
		else if(secondQueue.empty())
		{
			son2 = firstQueue.front();
			firstQueue.pop();
		}
		else
		{
			if(firstQueue.front() < secondQueue.front())
			{
				son2 = firstQueue.front();
				firstQueue.pop();
			}
			else
			{
				son2 = secondQueue.front();
				secondQueue.pop();
			}	
		}
		
		tree[++current].value = son1.times + son2.times;
		tree[current].leftSon = son1.posInTree;
		tree[current].rightSon = son2.posInTree;
		
		secondQueue.push(symbol(tree[current].value, current));
	}
	
	dfs(current);
	
	out << sum << '\n';
	for(int i=1 ; i<=num ; ++i)
		out << tree[i].leftSon << ' ' << tree[i].value << '\n';
	
	in.close();
	out.close();
	return 0;
}

void dfs(int node, ll currentCode, int codeLen)
{
	if(tree[node].leftSon)
	{
		dfs(tree[node].leftSon, currentCode<<1, codeLen+1);
		dfs(tree[node].rightSon, (currentCode<<1)+1, codeLen+1);
		return;
	}
	
	sum += tree[node].value * codeLen;
	tree[node].value = currentCode;
	tree[node].leftSon = codeLen;
}