#include<fstream>
#define LL long long
using namespace std;
const int Nmax = 1000005;
ifstream f("huffman.in"); ofstream g("huffman.out");
struct cuplu {LL cost; int poz;};
LL lg, bz[Nmax], val[2*Nmax];
int n, nr, fs[2*Nmax], fd[2*Nmax], nrbiti[Nmax];
cuplu q1[Nmax], q2[Nmax];
int pq1=1, uq1, pq2=1, uq2;
inline void cr(const cuplu &a, const cuplu &b)
{   //++nr; ++uq2;
    val[++nr]=q2[++uq2].cost=a.cost + b.cost;  q2[uq2].poz=nr; //t.cost = a.cost + b.cost; t.poz = ++nr;
    fd[nr] = a.poz; fs[nr] = b.poz;
    //val[nr] = t.cost;
    //q2[++uq2]=t;
}
inline void df(int nod, int niv, LL b10)
{   if(nod!=nr)lg += val[nod];
    if(nod<=n)
        { nrbiti[nod] = niv;  bz[nod] = b10; return;}
    df(fd[nod], niv+1, (b10<<1)+1);
    df(fs[nod], niv+1, (b10<<1));
}
int main()
{   cuplu t1,t2;
    f >> n;
    for(int i=1; i<=n; ++i)
        {   f >>val[i];
            //t.poz = i; t.cost = val[i];
            q1[++uq1].poz=i; q1[uq1].cost=val[i]; //q1.push(t);
        }
    nr = n;
    //t1=q1[pq1++]; //t1=q1.front(); q1.pop();
    //t2=q1[pq1++]; //t2=q1.front(); q1.pop();
    //cr(t1,t2);
    cr(q1[pq1++],q1[pq1++]);
    while(pq1<=uq1) //while(!q1.empty())
    {   if(q1[pq1].cost > q2[pq2].cost)  //if(q1.front().cost > q2.front().cost)
             {  //t1=q2[pq2++]; //t1 = q2.front(); q2.pop();
                if(pq2>=uq2) cr(q2[pq2++],q1[pq1++]);//t2=q1[pq1++];  //if(q2.empty()) {t2 = q1.front(); q1.pop();}
                    else  if(q1[pq1].cost > q2[pq2+1].cost) cr(q2[pq2++],q2[pq2++]);//t2=q2[pq2++];  //if(q1.front().cost > q2.front().cost) {t2 = q2.front(); q2.pop();}
                            else cr(q2[pq2++],q1[pq1++]);//t2=q1[pq1++]; //{t2 = q1.front(); q1.pop();}
             }
        else {  //t1=q1[pq1++]; //t1 = q1.front(); q1.pop();
                if(pq1>=uq1)cr(q1[pq1++],q2[pq2++]); //t2=q2[pq2++];//if(q1.empty()) {t2 = q2.front(); q2.pop();}
                    else if(q1[pq1+1].cost > q2[pq2].cost) cr(q1[pq1++],q2[pq2++]); //t2=q2[pq2++]; //if(q1.front().cost > q2.front().cost) {t2 = q2.front(); q2.pop();}
                            else cr(q1[pq1++],q1[pq1++]);//t2=q1[pq1++]; //{t2 = q1.front(); q1.pop();}
             };
       // cr(t1,t2);
    };
    while(pq2<uq2)//while(q2.size()>1)
    {
        //t1=q2[pq2++];//t1 = q2.front(); q2.pop();
        //t2=q2[pq2++]; //t2 = q2.front(); q2.pop();
        cr(q2[pq2++],q2[pq2++]);
    }
    df(nr,0,0);
    g << lg << "\n";
    for(int i=1; i<=n; ++i)
        g << nrbiti[i] << " " << bz[i] << "\n";
    g.close(); return 0;
}