#include <iostream>
#include <fstream>

#define maxn 1000001

const uint64_t inf = 0x7fffffffffffffff;

using namespace std;

struct node
{
    uint64_t lu;
    union
    {
        struct
        {
            uint64_t st;
            uint64_t dr;
        };

        uint64_t f[2];
    };
};

//queue stuff
node q[2 * maxn];
int st1, dr1;
int st2, dr2;


uint64_t lg[maxn], codes[maxn];
uint64_t T; //total cost
int N; //number of chars

void DF (int k, uint64_t code, int lvl)
{
    //cout<<"DF on node "<<k<<"\n";
    if(q[k].st && q[k].dr)
    {
            DF(q[k].st, code * 2, lvl + 1);
            DF(q[k].dr, code * 2 + 1, lvl + 1);
            return;
    }
    lg[k] = lvl;
    codes[k] = code;
}

int main()
{
    ifstream in ("huffman.in");
    ofstream out ("huffman.out");

    in>>N;
    for(int i = 1; i <= N; ++i)      //read all the frequencies and place them in the Q asap because they are already sorted
        in>>q[i].lu;

     for(int i = N + 1; i < 2 * N; ++i)
        q[i].lu = inf;

    st1 = 1;
    dr1 = N + 1;    //first Q boundary

    st2 = N + 1;
    dr2 = st2;  //second Q boundary

    for(int i = 1; i < N; ++i)
    {
        node temp;
        temp.lu = 0;
        temp.st = 0;
        temp.dr = 0;

        //cout<<"Step "<<i<<"\n";
        for(int j = 0; j < 2; ++j)
        {
            if((dr1 - st1) && (dr2 - st2))  //both queues are not empty
            {
                if(q[st1].lu < q[st2].lu)     //take new character
                {
                    temp.lu += q[st1].lu;
                    temp.f[j] = st1;
                    ++st1;
                }

                else                //take intermediate node
                {
                    temp.lu += q[st2].lu;
                    temp.f[j] = st2;
                    ++st2;
                }
            }

            else
            {
                if(dr1 - st1)
                {
                    temp.lu += q[st1].lu;
                    temp.f[j] = st1;
                    ++st1;
                }

                else
                {
                    temp.lu += q[st2].lu;
                    temp.f[j] = st2;
                    ++st2;
                }
            }
        }
        //cout<<"Generated a new node with freq "<<temp.lu<<" and with sons "<<temp.st<<", "<<temp.dr<<"\n";
        T += temp.lu;
        q[dr2] = temp;
        ++dr2;
    }

    out<<T<<"\n";
    DF(2 * N - 1, 0, 0);
    for(int i = 1; i <= N; ++i)
        out<<lg[i]<<" "<<codes[i]<<"\n";

    return 0;
}