#include <fstream>
#include <vector>
#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{
    int val;
    int poz;
    nod *L,*R;
    nod(int _val,int _poz,nod *_L,nod *_R) : val(_val) , poz(_poz) , L(_L) , R(_R){};
};

vector<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(int &A,int &B)
{
    if (A<Q1.size() && B<Q2.size())
    {
        if (Q1[A]->val<Q2[B]->val)
            return Q1[A++];
        else
            return Q2[B++];
    }
    else if (A<Q1.size())
        return Q1[A++];
    return Q2[B++];
}

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()>A+B+1)
    {
        nod *a,*b;
        a = popMinim(A,B);
        b = popMinim(A,B);

        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;
}