#include <fstream>
using namespace std;
typedef long long LL;
const int NMAX=1000005;
struct nod
{ 
       int l,r;
       LL w;
       nod() {}
       nod(int l,int r,LL w)
       {
               this->l=l;
               this->r=r;
               this->w=w; 
       }
};
nod G[2*NMAX];
int N,p1,u1,p2,u2,Q1[NMAX],Q2[NMAX];
void citeste()
{
     int i;
     LL x;
     ifstream f("huffman.in");
     f>>N;
     p1=1;u1=0;
     for (i=1;i<=N;++i)
     {
         f>>x;
         G[i]=nod(0,0,x);
         Q1[++u1]=i;
     }
}
int Extract()
{
    if (p1>u1) return Q2[p2++];
    if (p2>u2) return Q1[p1++];
    if (G[Q1[p1]].w < G[Q2[p2]].w) return Q1[p1++];
    return Q2[p2++];
}
void solve()
{
     int i,n=N,u,v;
     p2=1;u2=0;
     for (i=1;i<N;++i)
     {
           u=Extract();
           v=Extract();
           G[++n]=nod(u,v,G[u].w+G[v].w);
           Q2[++u2]=n;
     }
}
int L[NMAX];
LL B[NMAX];
void df(int n,int len,LL cod)
{
     if (!G[n].l)
     {
        L[n]=len;
        B[n]=cod;
        return;
     } 
     df(G[n].l,len+1,cod*2);
     df(G[n].r,len+1,cod*2+1);
}
void scrie()
{
     ofstream f("huffman.out");
     LL LG=0;
     int i;
     for (i=1;i<=N;++i) LG+=G[i].w*L[i];
     f<<LG<<'\n';
     for (i=1;i<=N;++i) f<<L[i]<<' '<<B[i]<<'\n';
}
int main()
{
    citeste();
    solve();
    df(2*N-1,0,0);
    scrie();
    return 0;
}