#include <fstream>
#include <vector>
using namespace std;

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

const long long inf =  1LL * 1000000000 * 1000000000;
const int maxn=100100;
struct node
{
    long long freq;
    long f[2];
}huff[2*maxn];
long lg[maxn],q[2][maxn];
long long b[maxn];


void print(long poz,long long cod,long level)
{
    if(huff[poz].f[0])
    {
        print(huff[poz].f[0],2*cod,level+1);
        print(huff[poz].f[1],cod*2+1,level+1);
        return;
    }
    lg[poz]=level;
    b[poz]=cod;

}

void huffman(long n)
{
    long k=n;
    long r[2],l[2];
    l[0]=l[1]=1;
    r[0]=n,r[1]=0;
    long long sol=0,min;
    long p;
    while(l[0]+l[1]<=r[0]+r[1])
    {
        ++k;
        for(int j=0;j<2;j++)
        {
            p=0;
            min=inf;
            for(int i=0;i<2;i++)
            {
                if(huff[q[i][l[i]]].freq<min && l[i]<=r[i])
                {
                    p=i;
                    min=huff[q[i][l[i]]].freq;
                }
            }
            huff[k].f[j]=q[p][l[p]];
            huff[k].freq+=huff[q[p][l[p]]].freq;
            l[p]++;
        }
        sol+=huff[k].freq;
        q[1][++r[1]]=k;
    }
    print(k,0,0);
    ki<<sol<<endl;
}

int main()
{
    long n;
    be>>n;
   /* vector<node>huff(2*n+100);
    vector<long>lg(n+100);
    vector<long long>b(n+100);
    vector<vector<long> >q(2,vector<long>(n+100));*/
    for(int i=1;i<=n;i++)
    {
        be>>huff[i].freq;
        q[0][i]=i;
    }
    huffman(n);
    for(int i=1;i<=n;i++)
    {
        ki<<lg[i]<<" "<<b[i]<<endl;
    }
    return 0;
}