#include <fstream>
#include <queue>
#include <climits>
#define uni unsigned int
#define ull unsigned long long
#define w 2000002
using namespace std;
queue <uni> q1;
queue <uni> q2;
uni frec[w];
uni v[w][2];
uni sol;ull lg[w],b[w];
void df(uni x, ull cod, ull niv)
{
    if (v[x][0])
    {
        df(v[x][0],2*cod,niv+1);
        df(v[x][1],2*cod+1,niv+1);
        return;
    }
    lg[x]=niv;
    b[x]=cod;
}
void huff(uni n)
{
    uni i,j,k=n,p,x;ull min;
    for (j=1;j<=n-1;j++)
    {
        k++;
        /* adaugam un nod k, tatal celor mai
        mici 2 elemente din cele 2 cozi*/
        for (i=0;i<=1;i++)
        {
            min=ULLONG_MAX;
            if (!q1.empty())
            {
                x=q1.front();
                if (frec[x]<min)
                {
                    min=frec[x];
                    p=1;
                }
            }
            if (!q2.empty())
            {
                x=q2.front();
                if (frec[x]<min)
                {
                    min=frec[x];
                    p=2;
                }
            }
            if (p==1)
            {
                x=q1.front();
                q1.pop();
                v[k][i]=x;
                frec[k]+=frec[x];
            }
            else
            {
                x=q2.front();
                q2.pop();
                v[k][i]=x;
                frec[k]+=frec[x];
            }
        }
        sol+=frec[k];
        q2.push(k);
    }
    df(k,0,0);
}
int main()
{
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    uni i,n;
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>frec[i];
        q1.push(i);
    }
    huff(n);
    g<<sol<<'\n';
    for (i=1;i<=n;i++)
    {
        g<<lg[i]<<' '<<b[i]<<'\n';
    }
    f.close();
    g.close();
    return 0;
}