#include<fstream>
#include<deque>


#define INF 1000000000000000000LL
#define N 1000100

using namespace std;

ifstream f("huffman.in");
ofstream g("huffman.out");

int n,i,x,m,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 pair<long long,int> iaper(){
    pair<long long,int>x,y;

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

    if(b0 <= b1)
        y = b[b0];
    else
        y = make_pair(INF,0);

    if(x < y)
    {
        ++a0;

        return x;
    }
    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;

        return;
    }

    dfs(fi[x].first, niv + 1, cod * 2);
    dfs(fi[x].second, niv + 1, cod * 2 + 1);
}

int main()
{
    f >> n;

    for(i = 1; i <= n; ++i)
    {
        f >> v[i];

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

    a0 = b0 = 1;

    m = n;

    for(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(i = 1; i <= n; ++i)
        g << l[i] << ' ' << c[i] <<'\n';

    return 0;
}