#include <bits/stdc++.h>
#define N 2000011
#define bb {F[++T]=F[b]+F[b+1];sol+=F[T];S[T]=b;D[T]=b+1;b+=2;}
#define BB {F[++T]=F[B]+F[B+1];sol+=F[T];S[T]=B;D[T]=B+1;B+=2;}
#define bB {F[++T]=F[b]+F[B];sol+=F[T];S[T]=b;D[T]=B;b++;B++;}
ifstream f("huffman.in");
ofstream g("huffman.out");
int n,i,j,k,b,B,t,T,S[N],D[N],L[N];
long long sol,F[N],C[N];
void read(),solve();
int main()
{
    f>>n;
    for(i=1;i<=n;i++)
        f>>F[i];
    sol=F[n+1]=F[1]+F[2];
    S[n+1]=1;D[n+1]=2;
    b=3;t=n;B=T=n+1;
    for(;b<t;)
    {
        if(B<T)
        {
            if(F[b+1]<=F[B])bb
            else if(F[B+1]<=F[b])BB
            else bB
        }
        else if(B==T)
        {
            if(F[b+1]<=F[B]) bb
            else bB
        }
        else bb;
    }
    for(;b==t&&B<=T;)
    {
        if(B<T)
        {
            if(F[B+1]<=F[b]) BB
            else bB
        }
        else bB;
    }
    for(;B<T;)BB
    g<<sol<<'\n';
    for(i=T;i>n;i--)
    {
        L[S[i]]=L[D[i]]=L[i]+1;
        C[S[i]]=2*C[i];
        C[D[i]]=2*C[i]+1;
    }
    for(i=1;i<=n;i++)
        g<<L[i]<<' '<<C[i]<<'\n';
    return 0;
}