#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;
    int 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;

int lun[Nmax];i64 code[Nmax];

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

    if ( nod <= N )
    {
        lun[nod] = Depth;
        code[nod] = Key;
        return;
    }

    Get(H[nod].left,Key*2LL+0LL,Depth+1);
    Get(H[nod].right,Key*2LL+1LL,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;
            fr.pop();
        }
        else
        {
            p.val += gr.front().val;
            H[p.key].left = gr.front().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;
            fr.pop();
        }
        else
        {
            p.val += gr.front().val;
            H[p.key].right = gr.front().key;
            gr.pop();
        }

        if ( H[p.key].left > H[p.key].right )
            swap( H[p.key].left , H[p.key].right );

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

    Get( K,0LL,0 );

    G<<Out<<'\n';
    for (int i=1;i<=N;++i)
        G<<lun[i]<<' '<<code[i]<<'\n';
}