#include <fstream>
#include <vector>
#include <algorithm>
#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*> H;

struct REZ{
    int lg;
    LL val;

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

bool comp(nod *a,nod *b)
{
    return a->val>b->val;
}

template<typename T>
void mypop (vector<T> &H)
{
    pop_heap(H.begin(),H.end(),comp);
    H.pop_back();
}

template<typename T>
void mypush (vector<T> &H, T val)
{
    H.push_back(val);
    push_heap(H.begin(),H.end(),comp);
}

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

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


    make_heap(H.begin(),H.end(),comp);

    while (H.size()>1)
    {
        nod *a = H[0];
        mypop<nod*> (H);
        nod *b = H[0];
        mypop<nod*> (H);

        nod *c = new nod(a->val+b->val,-1,a,b);
        mypush<nod*> (H,c);
    }

    g<<dfs(H[0],0,0) - H[0]->val<<'\n';

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

    return 0;
}