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

using namespace std;

#define maxn 1000100
#define inf 1LL * 1000000000 * 1000000000

struct Node{
	long long value;
	long right,left;
};

typedef struct Node *tNode;

tNode nd[2*maxn];
int q1[maxn],q2[maxn];
int n,w1=1,w2=1,t2;
long long b10[maxn];
long lg[maxn]; 
ofstream out("huffman.out");


tNode createNode(long long val, long left, long right){
	tNode node=new Node();
	node->value=val;
	node->right=right;
	node->left=left;
	return node;
}


long m(){
	long long value1=inf,value2=inf;
	long sol;
	if(w1<=n)
		value1=nd[q1[w1]]->value; 
	if(w2!=t2 && t2!=0)
	    value2=nd[q2[w2]]->value;
	if(value1<value2){
		sol=q1[w1];
        w1++;
	}	
	else{
		sol=q2[w2];
        w2++;
	}
	return sol;
}


long buildTree(){
	ifstream in("huffman.in");
	int i,k;
	tNode node1, node2;
	long long x,lg=0; 
	in>>n; 
	
	for(i=1;i<=n;i++) {
		in>>x;
		nd[i]=createNode(x,0,0);
		q1[i]=i;
	}  
	in.close();
	
	k=n;
	bool ok=true;
	while(w1<n || ok){  
	   k++; 
	   long left=m(); 
	   long right=m();
	   lg+=nd[left]->value+nd[right]->value;
	   nd[k]=createNode(nd[left]->value+nd[right]->value,left,right);
	   t2++;
	   q2[t2]=k;
	   if(w2==t2 && t2!=0 && w1>=n) ok=0;
	}
	out<<lg<<'\n';
	return q2[t2]; 
}


void readTree(long poz, long long cod, long nivel){
	if(nd[poz]->left==0){
		lg[poz]=nivel;
		b10[poz]=cod;
	}
	if(nd[poz]->left!=0)
	    readTree(nd[poz]->left,cod*2,nivel+1);     
	if(nd[poz]->right!=0)
	    readTree(nd[poz]->right,cod*2+1,nivel+1);
}


int main(){
    readTree(buildTree(),0,0);	
	for(int i=1;i<=n;i++) 
	   out<<lg[i]<<" "<<b10[i]<<'\n';    
    return 0;
}