#include <fstream>
#include <iostream>
#include <algorithm>
#include <queue>

#define MAXN 1000001

using namespace std;

int n, result;
int huffman_length[MAXN];
int huffman_code[MAXN];

typedef struct node {
	struct node *left, *right;
	int weight, info;

	node(int weight, int info) {
		this->weight = weight;
		this->info = info;
		this->left = NULL;
		this->right = NULL;
	}
} Node;

queue<Node*> Q1, Q2;

void read() {
	ifstream f("huffman.in");
	f >> n;
	int x;
	Node *current;
	for(int i = 0; i < n; i++){
		f >> x;
		current = new Node(x, i);
		Q1.push(current);
	}
	f.close();
}

Node* get_smallest_node() {
	Node *ret = NULL;
	Node *node1 = NULL, *node2 = NULL;
	// remove smallest from the two queues
	if (!Q1.empty())
		node1 = Q1.front();
	if (!Q2.empty())
		node2 = Q2.front();

	if (node1 && node2)
		ret = node1->weight < node2->weight ? node1 : node2;
	//assume that none of the queues is empty
	else
		ret = node1 ? node1 : node2;
	if (ret == node1)
		Q1.pop();
	else
		Q2.pop();
	
	return ret;
}

Node* create_huffman() {
	Node *root;
	Node *left, *right;
	while(Q1.size() + Q2.size() != 1) {
		left = get_smallest_node();
		right = get_smallest_node();
		root = new Node(left->weight + right->weight, -1);
		root->left = left;
		root->right = right;
		Q2.push(root);
	}	
	return Q2.front();
}
	
void get_encoding(Node *n, int code, int len) {
	if (n->info != -1) {
		result += len * n->weight;
		huffman_length[n->info] = len;
		huffman_code[n->info] = code;
	}
	if (n->left)
		get_encoding(n->left, code * 2, len + 1);
	if (n->right)
		get_encoding(n->right, code * 2 + 1, len + 1);
}

void write_result() {
	ofstream g("huffman.out");
	g << result << "\n";
	for (int i = 0; i < n; i++)
		g << huffman_length[i] << " " << huffman_code[i] << "\n";
	g.close();
}

int main(void) {
	read();
	Node *huffman = create_huffman();
	get_encoding(huffman, 0, 0);
	write_result();
	return 0;
}