#include <fstream>
#include <queue>

using namespace std;
ifstream f("huffman.in");
ofstream g("huffman.out");
int n,j,l[1000001];
long long nr[1000001];
typedef pair<long long,int> pere;
typedef pair<int, int> per;
queue<pere> q,s;
per a[2000002];
void reconstruire(int k, int nivel, long long cod)
{
    if(a[k].first)
    {reconstruire(a[k].first,nivel+1,cod*2);
     reconstruire(a[k].second,nivel+1,cod*2+1);}
     else
    {l[k]=nivel;
    nr[k]=cod;}
}
void huff()
{
    long long x,y,lg=0;
    pere k;
    j=n;
    while(!(q.empty() and s.size()==1))
   { j++;
     if(!q.empty() and (s.empty() or q.front().first<s.front().first))
      {
          x=q.front().first;
          a[j].first=q.front().second;
          q.pop();
      }
      else
      {
          x=s.front().first;
          a[j].first=s.front().second;
          s.pop();
      }
    if(!q.empty() and (s.empty() or q.front().first<s.front().first))
      {
          y=q.front().first;
          a[j].second=q.front().second;
          q.pop();
      }
      else
      {
          y=s.front().first;
          a[j].second=s.front().second;
          s.pop();
      }
   k.first=x+y;
   k.second=j;
   s.push(k);

   lg=lg+x+y;
   }
   g<<lg<<"\n";
}
void citire()
{
    pere x;
    int i;
    f>>n;
    for(i=1;i<=n;i++)
    {
        f>>x.first; //numar aparitii
        x.second=i; //numar caracter
        q.push(x);
    }
}
int main()
{
    citire();
    huff();
    reconstruire(j,0,0);
    int i;
  //  for(i=1;i<=j;i++)
  //   g<<i<<" "<<a[i].first<<" "<<a[i].second<<"\n";
    for(i=1;i<=n;i++)
     g<<l[i]<<" "<<nr[i]<<"\n";
    return 0;
}