#include <stdio.h>
#include <fstream>
#include <stack>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;

typedef char TChar;
typedef TChar *PChar;
typedef long long TTime;
#define DEBUGGING

#ifdef DEBUGGING
#include <windows.h>
#include <conio.h>

TTime CyclesPerSecond = 0;

void InitCycles(void)
{
 LARGE_INTEGER LI;
 QueryPerformanceFrequency(&LI);
 CyclesPerSecond = LI.QuadPart;
}

TTime GetCycles(void)
{
 LARGE_INTEGER LI;
 QueryPerformanceCounter(&LI);
 return LI.QuadPart;
}

void CyclesToTime(TTime Cycles,PChar Message)
{
 printf("%s : %lld\n",Message,(Cycles * 1000000) / CyclesPerSecond);
}

#else

void InitCycles(void)
{
}

TTime GetCycles(void)
{
 return 0;
}

void CyclesToTime(TTime,PChar)
{
}

#endif

long N;

struct TNod;
typedef TNod *PNod;
struct TNod
{
 PNod Left,Right;
 long Index;
 long Val;
};

long long T;
long long B[1000005];
long LenB[1000005];

long QFIn,QFOut;
long QNIn,QNOut;
PNod QFrunza[1000005];
PNod QNod[1000005];

long TNodPos;
TNod Nods[2000010];

char Transfer[12000000];
char *Input;

long ReadInt(char *&S)
{
 while ((*S) < '0')
  {
   S += 1;
  }
 long Res = 0;
 while ((*S) >= '0')
  {
   Res = (Res * 10) + ((*S) - '0');
   S += 1;
  }
 return Res;
}

void WriteInt(char *&S,long long n)
{
 if (n == 0)
   {
    S[0] = '0';
    S[1] = ' ';
    return;
   }
 char Data[40];
 long i = 0;
 while (n > 0)
  {
   Data[i] = (n % 10) + '0';
   n /= 10;
   i += 1;
  }
 for (i -= 1;i >= 0;i -= 1)
  {
   (*S) = Data[i];
   S += 1;
  }
 (*S) = ' ';
 S += 1;  
}

void PutNL(char *&S)
{
 S[-1] = '\n';
}

void ReadInput(void)
{
 FILE *FIN = fopen("huffman.in","rt");
 fseek(FIN,0,SEEK_END);
 long SS = ftell(FIN);
 fseek(FIN,0,SEEK_SET);
 fread(Transfer,1,SS,FIN);
 fclose(FIN);
}

void WriteOutput(void)
{
 FILE *FOUT = fopen("huffman.out","wt");
 fwrite(Transfer,1,Input - Transfer,FOUT);
 fclose(FOUT);
}

long minint(long a,long b)
{
 if (a < b)
   {
    return a;
   }
 return b;
}

void CreazaSolutie(PNod R,long CodLen,long long CodRep)
{
 if (R->Index >= 0)
   {
    LenB[R->Index] = CodLen;
    B[R->Index] = CodRep;
    T += ((long long)(R->Val)) * CodLen;
    return;
   }
 CreazaSolutie(R->Left,CodLen + 1,CodRep << 1);
 CreazaSolutie(R->Right,CodLen + 1,(CodRep << 1) | 1);
}

void AlegeNodMin(PNod &n1,PNod &n2)
{
 if ((QFIn - QFOut) == 0)
   {
    n1 = QNod[QNOut];
    n2 = QNod[QNOut + 1];
    QNOut += 2;
    return;
   }
 if ((QNIn - QNOut) == 0)
   {
    n1 = QFrunza[QFOut];
    n2 = QFrunza[QFOut + 1];
    QFOut += 2;
    return;
   }
 if (QFrunza[QFOut]->Val <= QNod[QNOut]->Val)
   {
    n1 = QFrunza[QFOut];
    QFOut += 1;
    if ((QFIn - QFOut) == 0)
      {
       n2 = QNod[QNOut];
       QNOut += 1;
       return;
      }
    if (QFrunza[QFOut]->Val <= QNod[QNOut]->Val)
      {
       n2 = QFrunza[QFOut];
       QFOut += 1;
      }
     else
      {
       n2 = QNod[QNOut];
       QNOut += 1;
      }
   }
  else
   {
    n1 = QNod[QNOut];
    QNOut += 1;
    if ((QNIn - QNOut) == 0)
      {
       n2 = QFrunza[QFOut];
       QFOut += 1;
       return;
      }
    if (QFrunza[QFOut]->Val <= QNod[QNOut]->Val)
      {
       n2 = QFrunza[QFOut];
       QFOut += 1;
      }
     else
      {
       n2 = QNod[QNOut];
       QNOut += 1;
      }
   }
}

int main(void)
{
 TTime T1,T2;
 InitCycles();
 long i;
 ReadInput();
 Input = Transfer;
 T1 = GetCycles();
 N = ReadInt(Input);
 for (i = 0;i < N;i += 1)
  {
   Nods[i].Index = i;
  }
 for (i = 0;i < N;i += 1)
  {
   QFrunza[i] = Nods + i;
  }
 QFIn = N;
 TNodPos = N;
 T2 = GetCycles();
 CyclesToTime(T2 - T1,"Init");
 T1 = GetCycles();
 for (i = 0;i < N;i += 1)
  {
   Nods[i].Val = ReadInt(Input);
  }
 T2 = GetCycles();
 CyclesToTime(T2 - T1,"Input");
 T1 = GetCycles();
 while ((QFIn != QFOut) || (QNIn != (QNOut + 1)))
  {
   PNod b1,b2,bn;
   AlegeNodMin(b1,b2);
   bn = Nods + TNodPos;
   TNodPos += 1;
   bn->Left = b1;
   bn->Right = b2;
   bn->Index = -1;
   bn->Val = b1->Val + b2->Val;
   QNod[QNIn] = bn;
   QNIn += 1;
  }
 T2 = GetCycles();
 CyclesToTime(T2 - T1,"Work");
 T1 = GetCycles();
 CreazaSolutie(QNod[QNOut],0,0);
 T2 = GetCycles();
 CyclesToTime(T2 - T1,"Prepare");
 T1 = GetCycles();
 Input = Transfer;
 WriteInt(Input,T);
 PutNL(Input);
 for (i = 0;i < N;i += 1)
  {
   WriteInt(Input,LenB[i]);
   WriteInt(Input,B[i]);
   PutNL(Input);
  }
 T2 = GetCycles();
 CyclesToTime(T2 - T1,"Output");
 WriteOutput();
 return 0;
}