#include <fstream>
#include <vector>
#include <deque>
#define pb push_back
#define LL long long
#define Nmax 1000001
using namespace std;

ifstream f("huffman.in");
ofstream g("huffman.out");

int n,x;

struct nod{
    LL val;
    int poz;
    nod *L,*R;
    nod(LL _val,int _poz,nod *_L,nod *_R) : val(_val) , poz(_poz) , L(_L) , R(_R){};
};

deque<nod*> Q1,Q2;

struct REZ{
    int lg;
    LL val;

    REZ(int _lg,LL _val) : lg(_lg) , val(_val){};
};
REZ rez[Nmax] = REZ(0,0);

LL dfs(nod *N,LL val,int lg)
{
    LL LG = 0;
    if (N->poz!=-1)
        rez[N->poz] = REZ(lg,val);
    if (N->L!=NULL)
        LG = dfs(N->L,val<<1,lg+1);
    if (N->R!=NULL)
        LG = LG + dfs(N->R,(val<<1)+1,lg+1);
    return LG+N->val;
}

nod* popMinim()
{
    nod* aux;
    if (!Q1.empty() && !Q2.empty())
    {
        if (Q1.front()->val<Q2.front()->val)
        {
            aux = Q1.front();
            Q1.pop_front();
            return aux;
        }
        else
        {
            aux = Q2.front();
            Q2.pop_front();
            return aux;
        }
    }
    else if (!Q1.empty())
    {
        aux = Q1.front();
        Q1.pop_front();
        return aux;
    }
    aux = Q2.front();
    Q2.pop_front();
    return aux;
}

int main()
{
    f>>n;
    for (int i=1;i<=n;i++)
    {
        f>>x;
        Q1.push_back(new nod(x,i,NULL,NULL));
    }
    if (n==1)
    {
        g<<x<<'\n';
        g<<"1 0\n";
        return 0;
    }

    int A = 0,B = 0;
    while (Q1.size()+Q2.size()>1)
    {
        nod *a,*b;
        a = popMinim();
        b = popMinim();

        Q2.push_back(new nod(a->val+b->val,-1,a,b));
    }

    g<<dfs(Q2.back(),0,0) - Q2.back()->val<<'\n';

    for (int i=1;i<=n;i++)
        g<<rez[i].lg<<' '<<rez[i].val<<'\n';

    return 0;
}