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



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


void print(int poz,long long cod,int 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(int 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);
    printf("%lld\n",sol);
}

int main()
{
    freopen("huffman.in","r",stdin);
    freopen("huffman.out","w",stdout);
    int n;
    scanf("%d",&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++)
    {
        scanf("%lld",&huff[i].freq);
        q[0][i]=i;
    }
    huffman(n);
    for(int i=1;i<=n;i++)
    {
        printf("%d %lld\n",lg[i],b[i]);
    }
    return 0;
}