#include<fstream>
#include<deque>


#define INF 1000000000000000000LL
#define N 1000100
#define D 50000

using namespace std;

ofstream g("huffman.out");

int n,i,x,m,poz = D,a0,a1,b0,b1,l[N],v[N];

long long c[N],lg;

pair<long long,int> a[N],b[N];

pair<int,int>fi[2 * N];
pair<long long, int>fs,fd;

inline iaper(pair<long long,int> &x){
    long long v1,v2;

    if(a0 <= a1)
        x = a[a0];
    else
        x = make_pair(INF,0);

    if(b0 <= b1)
        x = min(x,b[b0]);

    if(x < y)
    {
        ++a0;

        ret
    }
    else
    {
        ++b0;

        return y;
    }
}

inline void dfs(int x,int niv,long long cod){
    if(x <= n)
        lg += niv * v[x],

        c[x] = cod,
        l[x] = niv;
    else
        dfs(fi[x].first, niv + 1, cod << 1),
        dfs(fi[x].second, niv + 1, (cod << 1) | 1);
}

int main()
{
    freopen("huffman.in","r",stdin),

    scanf("%d",&n);

    for(int i = 1; i <= n; ++i)
    {
        scanf("%d",&v[i]);

        a[++a1] = make_pair(1LL * v[i],i);
    }

    a0 = b0 = 1,

    m = n;

    for(int i = 1; i < n; ++ i)
    {
        fs = iaper(),
        fd = iaper(),

        fi[++m] = make_pair(fs.second, fd.second),

        b[++b1] = make_pair(fs.first + fd.first, m);
    }

    dfs(m,0,0),

    g << lg << '\n';

    for(int i = 1; i <= n; ++i)
        g << l[i] << ' ' << c[i] <<'\n';

    return 0;
}