#include <iostream>
#include <fstream>
#include <queue>
struct nod
{
  int countt;
  long b;
  long long c;
  int l[2];
};

nod v[2005000];
std::ifstream fin("huffman.in");
std::ofstream fout("huffman.out");
int n;
int countt;
std::queue<int> q1;
std::queue<int> q2;
long long sum;
void get(std::queue<int> & q, int & v1)
{
  v1= q.front();
  q.pop();
}
inline void travel(nod n1)
{
  for(int i=0;i<2;i++)
    if(n1.l[i]!=-1)
    {
      v[n1.l[i]].b=(n1.b<<1)+i;
      v[n1.l[i]].countt=n1.countt+1;
      travel(v[n1.l[i]]);
    }
}

int main()
{
  fin>>n;
  for(int i=0;i<n;i++)
  {
    int j;
    fin>>j;
    v[i]={0,0,j,{-1,-1}};
    q1.push(i);
  }
  countt=n;
  while(!q1.empty() || q2.size()>1)
  {
    int v1[2];
    for(int i=0;i<2;i++)
    {
      if(q1.empty()|| (!q2.empty() && v[q1.front()].c>v[q2.front()].c))
        get(q2,v1[i]);
      else
        get(q1,v1[i]);
    }
    long long v0c=v[v1[0]].c;
    long long v1c=v[v1[1]].c;
    v[countt]={0,0,v0c+v1c,{v1[0],v1[1]}};
    q2.push(countt);
    sum+=v0c+v1c;
    countt++;
  }
  travel(v[countt-1]);
  fout<<sum<<"\n";
  for(int i=0;i<n;i++)
    fout<<v[i].countt<<" "<<v[i].b<<"\n";
}