#include <bits/stdc++.h>

using namespace std;
const int nmax=1000005;
vector< pair<int,long long> > codes;
long long v[nmax];
int son[2*nmax][2];
int n;
long long answer;
void dfs(int node,long long code,int len){
    if(node<=n){
         answer+=1LL*len*v[node];
         codes[node-1]={len,code};
         return;
    }
    for(int i=0;i<2;i++)
        dfs(son[node][i],1LL*code*2+i,len+1);
}
int main()
{
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    queue< pair<int,int> > symbols,intern;
    f>>n;
    codes.resize(n);
    for(int i=1;i<=n;i++){
        f>>v[i];
        symbols.push({v[i],i});
    }
    int index=n;
    while(symbols.size()+intern.size()>1){
        int cost=0;
        index++;
        for(int take=0;take<2;take++){
            pair<int,int> added;
            if(symbols.empty()||((!intern.empty())&&intern.front().first<symbols.front().first)){
                    added=intern.front();
                    intern.pop();
            }
            else{
                 added=symbols.front();
                 symbols.pop();
            }
            cost+=added.first;
            son[index][take]=added.second;
        }
        intern.push({cost,index});
    }
    dfs(index,0,0);
    g<<answer<<'\n';
    for(auto code : codes)
        g<<code.first<<' '<<code.second<<'\n';
    return 0;
}