#include <iostream>
#include <list>
#include <fstream>
using namespace std;

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

struct nod{
    long long val;
    int left_son;
    int right_son;
}ab[2000001];

int n,p;
long long c[2000001][2];;
list <nod> a;
list <nod> b;

void init()
{
    nod x;
    in>>n;
    for (int i=1; i<=n; i++)
    {
        in>>x.val;
        x.left_son=NULL;
        x.right_son=NULL;
        a.push_back(x);
    }
}

nod extract_min()
{
    nod x,y;
    if (b.size()>0)
    {
        x=a.front();
        y=b.front();
        if ( x.val<=y.val ) { a.pop_front(); return x; } else { b.pop_front(); return y; }
    } else
    {
        x=a.front();
        a.pop_front();
        return x;
    }
}


void huffman()
{
    long long sum=0;
    nod x,y,z; p=0;
    for (int i=1; i<=n-1; i++)
    {
        x=extract_min();
        y=extract_min();
        ab[++p]=x;
        z.left_son=p;
        ab[++p]=y;
        z.right_son=p;
        z.val=x.val+y.val;
        b.push_back(z);
        sum=sum+z.val;
    }
    ab[++p]=b.front();
    out<<sum<<endl;
}

void back(int p,long long s,int k)
{
    if (ab[p].left_son==NULL && ab[p].right_son==NULL) { c[p][0]=k+1; c[p][1]=s;} else
    {
        k++;
        back(ab[p].left_son,s*2,k);
        back(ab[p].right_son,s*2+1,k);
    }
}

int main()
{
    init();
    huffman();
    back(p,0,-1);
    for (int i=1; i<=n; i++) out<<c[i][0]<<" "<<c[i][1]<<endl;
    return 0;
}