#include <fstream>
#include<string>
using namespace std;
#define maxn 1000100
#define inf 1LL * 1000000000 * 1000000000
struct nod{
        long long v;
         long f[2];
        } nod[2*maxn];
long n, i, j, k, p, l[2], r[2];
long q[2][maxn], lg[maxn];
long long b[maxn], m, sol;
string s;

void df(long poz, long long cod, long nivel){
 if(nod[poz].f[0]){
        df(nod[poz].f[0], cod*2, nivel+1);
          df(nod[poz].f[1], cod*2+1, nivel+1);
         return;
        }
  lg[poz]=nivel;
  b[poz]=cod;
}

void solve(){
  k=n;
   l[0]=l[1]=1;
    r[0]=n;
  while(l[0]+l[1]<=r[0]+r[1]){
   ++k;
    for(j=0; j<2; j++) {
     p=0;
      m=inf;
     for(i=0; i<2; i++){
      if(nod[q[i][l[i]]].v<m && l[i]<=r[i]){
     p=i;
     m=nod[q[i][l[i]]].v;
      }
}
   nod[k].f[j]=q[p][l[p]];
    nod[k].v+=nod[q[p][l[p]]].v;
   l[p]++;
}
   sol+=nod[k].v;
q[1][++r[1]]=k;
}
df(k, 0, 0);
}            
int main(void){
  ifstream fin("huffman.in");
   ofstream fout("huffman.out");
  fin>>n; getline(fin,s); n=0; int i,j,l,x;
       getline(fin,s,char(EOF)); i=j=0; l=s.length();
        while(j<l) {    
                    x=0;
                    while(s[j]!='\n' && j<l)x=(x*10)+(s[j++]-'0');
                    nod[++n].v=x; q[0][n]=n; ++j; 
                    } 
   solve();
  fout<<sol<<"\n";;
   for(i=1; i<=n; i++)fout<<lg[i]<<" "<<b[i]<<"\n";
return 0;
}