// Coduri Huffman - Heap

#include <iostream>
#include <fstream>
#define NMAX 1000011
using namespace std;
struct nod{
       long long frecv;
       int st,dr;
       }nod[2*NMAX];
struct heap{
       int poz;
       long long val;
       }h[NMAX],aux;
int l,n;
long long lg[NMAX],b[NMAX];
void up(int pos)
{
     while(pos>1 && h[pos/2].val>h[pos].val)
     {
      aux=h[pos], h[pos]=h[pos/2], h[pos/2]=aux;
      pos=pos/2;
     }
}
void down(int pos)
{
     while((pos*2<=l && h[pos].val>h[pos*2].val) || (pos*2+1<=l && h[pos].val>h[pos*2+1].val))
     {
      if(h[pos*2].val<h[pos*2+1].val || pos*2+1>l)
      {
       swap(h[pos],h[pos*2]);
       pos=pos*2;
      }
      else
      {
       swap(h[pos],h[pos*2+1]);
       pos=pos*2+1;
      }               
     }
}
void introduce_in_heap(int x,int pos)
{
     l++;
     h[l].val=x;
     h[l].poz=pos;
     up(l);
}
int scoate_radacina_heap(int &pos)
{
    int x;
    x=h[1].val;
    pos=h[1].poz;
    h[1]=h[l];
    l--;
    down(1);
    return x;
}
void df(int pos, int cod, int nivel)
{
     if(nod[pos].st)
     {
      df(nod[pos].st,cod*2,nivel+1);
      df(nod[pos].dr,cod*2+1,nivel+1);
      return;
     }
     lg[pos]=nivel;
     b[pos]=cod;
}
int main()
{
    int i,x,x1,x2,poz1,poz2,k;
    long long s;
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    f>>n;
    for(i=1;i<=n;i++)
    {
     f>>x;
     nod[i].frecv=x;
     introduce_in_heap(x,i);
    }
    k=n; s=0;
    while(l>1)
    {
     x1=scoate_radacina_heap(poz1);
     x2=scoate_radacina_heap(poz2);
     nod[++k].frecv=x1+x2;
     nod[k].st=poz1;
     nod[k].dr=poz2;
     s+=nod[k].frecv;
     introduce_in_heap(nod[k].frecv,k);
    }
    df(k,0,0);
    g<<s<<"\n";
    for(i=1;i<=n;i++)
     g<<lg[i]<<" "<<b[i]<<"\n";
    return 0;
}