#include <fstream>
#include <queue>
#include <climits>
#define ull unsigned long long
#define w 1001000
using namespace std;
queue <long> q1;
queue <long> q2;
long frec[2*w-1];
long v[2*w-1][2];
ull sol;ull lg[w],b[w];
void df(ull 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);
    }
    else
    {
        lg[x]=niv;
        b[x]=cod;
    }
}
void huff(long n)
{
    long i,j,k=n,p,x,mini;
    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++)
        {
            mini=1LL*w*w;
            if (!q1.empty())
            {
                x=q1.front();
                if (frec[x]<mini)
                {
                    mini=frec[x];
                    p=1;
                }
            }
            if (!q2.empty())
            {
                x=q2.front();
                if (frec[x]<mini)
                {
                    mini=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");
    long 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;
}