#include <fstream>
#include <queue>
using namespace std;

const int Nmax = 1000010;

#define val first
#define key second

typedef long long i64;
typedef pair<i64,int> Pair;

typedef struct
{
    i64 val,key;
    int depth,dad,left,right;
} huff;

ifstream F("huffman.in");
ofstream G("huffman.out");

int N,K;
int A[Nmax];
queue<Pair> fr;
queue<Pair> gr;
huff H[Nmax<<1];
i64 Out;

void Get(int nod,i64 Key,int Depth)
{
    if ( H[nod].left || H[nod].right ) Out += H[nod].val;

    H[nod].key = Key;
    H[nod].depth = Depth;

    if ( H[nod].left != 0 ) Get(H[nod].left,Key*2+0,Depth+1);
    if ( H[nod].right != 0 ) Get(H[nod].right,Key*2+1,Depth+1);
}

int main()
{
    F>>N;
    for (int i=1;i<=N;++i)
        F>>A[i];

    for (int i=1;i<=N;++i)
    {
        fr.push( make_pair( A[i] , i ) );
        H[i].val = A[i];
        H[i].right = H[i].left = 0;
    }

    K = N;
    while ( gr.size() > 1 || fr.size() > 0 )
    {
        Pair p = make_pair( 0 , ++K );
        if ( ( fr.front() <= gr.front() && fr.size() > 0 ) || ( fr.size() > 0 && gr.size() == 0 ) )
        {
            p.val += fr.front().val;
            H[p.key].left = fr.front().key;
            H[fr.front().key].dad = p.key;
            fr.pop();
        }
        else
        {
            p.val += gr.front().val;
            H[p.key].left = gr.front().key;
            H[gr.front().key].dad = p.key;
            gr.pop();
        }

        if ( ( fr.front() <= gr.front() && fr.size() > 0 ) || ( fr.size() > 0 && gr.size() == 0 ) )
        {
            p.val += fr.front().val;
            H[p.key].right = fr.front().key;
            H[fr.front().key].dad = p.key;
            fr.pop();
        }
        else
        {
            p.val += gr.front().val;
            H[p.key].right = gr.front().key;
            H[gr.front().key].dad = p.key;
            gr.pop();
        }

        H[p.key].val = p.val;
        gr.push( p );
    }

    Get( K,0,0 );

    G<<Out<<'\n';
    for (int i=1;i<=N;++i)
    {
        G<<H[i].depth<<' ';
        G<<H[i].key<<'\n';
    }
}