#include<stdio.h>
#include<stdlib.h>

#include<vector>
#include<queue>
#include<set>

using namespace std;

#define NMAX 1000000

long long b;
unsigned char lb;

long long lung;

typedef struct nod{
	int parent, left, right; 
}nod; 

//long long freq;

vector<nod> huff; // arborele Huffman

struct index_cost {
	int index;
	long long cost;
};

struct pair_compare {
    bool operator() (const std::pair<long long,index_cost> & p1, const std::pair<long long,index_cost> & p2) const {
		if(p1.first == p2.first)
			return (p1.second.index < p2.second.index);
		else
			return (p1.first < p2.first);
    }
};

set<pair<long long,index_cost>,pair_compare> freq; // first freq, second node

int N;

void huffman(){
	int n=N; 
	set<pair<long long,index_cost>,pair_compare>::iterator it;
	int i,j;
	long long fi,fj;

	while(n<(2*N-1)){ 
		long long cost=0;
		it=freq.begin(); 
		i=it->second.index; fi=it->first;
		cost+=(it->second.cost+fi);
		freq.erase(it);
		it=freq.begin(); 
		j=it->second.index; fj=it->first;
		cost+=(it->second.cost+fj);
		freq.erase(it);
		
		index_cost aux;
		aux.index=n; aux.cost=cost;
		freq.insert(make_pair(fi+fj,aux));

		huff[n].left=i; huff[n].right=j;
		huff[i].parent=n; huff[j].parent=n;
		
		n++;
	}
	lung=(*freq.begin()).second.cost;
	printf("%lld\n",lung);
}

void buildDictionary(){
	int node, parent;
	for(int i=0;i<N;i++){
	    node=i;
		lb=0, b=0;
	    while(node!=(2*N-2)){ // 254 este radacina!
	        parent=huff[node].parent;
	        if(huff[parent].left==node)
				lb++;
	        else{
				b+=(1LL<<lb);
				lb++;
	        }
	        node=parent; 
	    }
		printf("%d %lld\n",lb,b);
	}
}


int main(){
	freopen("huffman.in","rt",stdin);
	freopen("huffman.out","wt",stdout);
	
	scanf("%d",&N);
	huff.reserve(2*N-1);

	int f;

	index_cost aux;
	for(int i=0;i<N;i++){
		scanf("%d",&f);
		aux.index=i; aux.cost=0;
		freq.insert(make_pair(f,aux));
	}

	// initializare arbore
	nod Node={-1,-1,-1};
	for(int i=0;i<(2*N-1);i++){
		huff.push_back(Node);
	}

	huffman();
	buildDictionary();

	return 0;
}