/*#include <fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream fin("huffman.in");
ofstream fout("huffman.out");

struct lol{
    long long int copilmic;
    long long int copilmare;
    long long int val;
};

long long int codu[1000002];
int fr[1000002],adancimea[1000002];
vector <lol> G;
vector<long long int> fr2;
void bfs(int nod,  int adancime,long long int cod);
 int main()
{
    long long int n,i,lungime=0,k,j,maimic,indicemic,maimare,indicemare,el1,el2,radacina;
    fin>>n;
    lol x;
    for(i=0; i<n;i++)
        {
            fin>>fr[i];
            x.val=fr[i];
            x.copilmic=-1;
            x.copilmare=-1;
            G.push_back(x);
        }
    j=0;
    k=0;
    while(j<n || k<fr2.size())
    {
        el1=-1,el2=-1;
        if(j<n) el1=fr[j];
        if(k<fr2.size()) el2=fr2[k];
        if(el1!=-1 && (el1<=el2 || el2==-1)){
            maimic=el1;
            indicemic=j;
            j++;
        }
        else if(el2!=-1 && (el1>el2 || el1==-1)){
            maimic=el2;
            indicemic=n+k;
            k++;
        }

        el1=-1,el2=-1;
        if(j<n) el1=fr[j];
        if(k<fr2.size()) el2=fr2[k];
         if(el1!=-1 && (el1<=el2 || el2==-1)){
            maimare=el1;
            indicemare=j;
            j++;
        }
        else if(el2!=-1 && (el1>el2 || el1==-1)){
            maimare=el2;
            indicemare=n+k;
            k++;
        }
        if(el1==-1 && el2==-1) {
                radacina=indicemic;
                break;
        }
        lol nod_nou;
        nod_nou.val=maimic+maimare;
        nod_nou.copilmic=indicemic;
        nod_nou.copilmare=indicemare;

        G.push_back(nod_nou);
        fr2.push_back(nod_nou.val);
        lungime+=nod_nou.val;
    }
    fout<<lungime<<'\n';
    bfs(radacina,0,0);
    for(i=0;i<n;i++)
        fout<<adancimea[i]<<" "<<codu[i]<<'\n';
    return 0;
}

void bfs(int nod,  int adancime,long long int cod){
    queue <pair<int, pair<int, long long int>  >>q;
    q.push({nod,{ adancime, cod}});
    while(!q.empty()){
        nod=q.front().first;
        adancime=q.front().second.first;
        cod=q.front().second.second;
        q.pop();
        if(G[nod].copilmic==-1) //nod final
            {
                adancimea[nod]=adancime;
                codu[nod]=cod;
                return;
            }

        q.push({G[nod].copilmare,{ adancime+1, cod*2+1}});
        q.push({G[nod].copilmic,{ adancime+1, cod*2}});
    }
}*/
#include <fstream>
#include<vector>
using namespace std;
ifstream fin("huffman.in");
ofstream fout("huffman.out");

struct lol{
     int copilmic;
     int copilmare;
    long long int val;
};

int fr[1000002], adancimea[1000002];
long long codu[1000002];
vector <lol> G;
vector<long long int> fr2;
void bfs(int nod, int adancime,long long int cod);

int main()
{
    long long int n,i,lungime=0,k,j,maimic,indicemic,maimare,indicemare,el1,el2,radacina;
    fin>>n;
    lol x;
    for(i=0; i<n;i++)
        {
            fin>>fr[i];
            x.val=fr[i];
            x.copilmic=-1;
            x.copilmare=-1;
            G.push_back(x);
        }
    j=0;
    k=0;
    while(j<n || k<fr2.size())
    {
        el1=-1,el2=-1;
        if(j<n) el1=fr[j];
        if(k<fr2.size()) el2=fr2[k];
        if(el1!=-1 && (el1<=el2 || el2==-1)){
            maimic=el1;
            indicemic=j;
            j++;
        }
        else if(el2!=-1 && (el1>el2 || el1==-1)){
            maimic=el2;
            indicemic=n+k;
            k++;
        }

        el1=-1,el2=-1;
        if(j<n) el1=fr[j];
        if(k<fr2.size()) el2=fr2[k];
         if(el1!=-1 && (el1<=el2 || el2==-1)){
            maimare=el1;
            indicemare=j;
            j++;
        }
        else if(el2!=-1 && (el1>el2 || el1==-1)){
            maimare=el2;
            indicemare=n+k;
            k++;
        }
        if(el1==-1 && el2==-1) {
                radacina=indicemic;
                break;
        }
        lol nod_nou;
        nod_nou.val=maimic+maimare;
        nod_nou.copilmic=indicemic;
        nod_nou.copilmare=indicemare;

        G.push_back(nod_nou);
        fr2.push_back(nod_nou.val);
        lungime+=nod_nou.val;
    }
    fout<<lungime<<'\n';
    bfs(radacina,0,0);
    for(i=0;i<n;i++)
        fout<<adancimea[i]<<" "<<codu[i]<<'\n';
    return 0;
}

void bfs(int nod,  int adancime,long long int cod){
    if(G[nod].copilmic==-1) //nod final
        {
            adancimea[nod]=adancime;
            codu[nod]=cod;
            return;
        }

        bfs(G[nod].copilmare, adancime+1, cod*2+1);
        bfs(G[nod].copilmic, adancime+1, cod*2);

}