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

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

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

int n,p1,p2,p3;
long long c[2000001][2];

void init()
{
    in>>n;
    for (int i=1; i<=n; i++)
    {
        in>>a[i].val;
        a[i].left_son=NULL;
        a[i].right_son=NULL;
    }
    p1=1;
    p2=n+1;
    p3=n;
}

int exract_min()
{
    if (p2>p3) { p1++; return p1-1; } else
        if (a[p1].val<=a[p2].val && p1<=n) { p1++; return p1-1; } else { p2++; return p2-1; }
}

void huffman()
{
    long long x,y,sum=0;
    for (int i=1; i<=n-1; i++)
    {
        x=exract_min();
        y=exract_min();
        p3++;
        a[p3].val=a[x].val+a[y].val;
        sum=sum+a[p3].val;
        a[p3].left_son=x;
        a[p3].right_son=y;
    }
    out<<sum<<endl;
}

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

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