#include <iostream>
#include <fstream>
#include <queue>
#include <bitset>
#define NMAX 1000001
#include <stack>
#define BUFF_SIZE 100001

using namespace std;

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

struct node{
    long long int key;
    int left;
    int right;
};

char buff[BUFF_SIZE];
int pos = 0;

void Read(int &a)
{
    while (!isdigit(buff[pos]))
        if (++pos == BUFF_SIZE)
            in.read(buff, BUFF_SIZE), pos = 0;
    a = 0;
    while (isdigit(buff[pos]))
    {
        a = a * 10 + buff[pos] - '0';
        if (++pos == BUFF_SIZE)
            in.read(buff, BUFF_SIZE), pos = 0;
    }
}

queue<int> q1, q2;
bitset <2 * NMAX> mark;
stack <int> st;
node H[2 * NMAX];
int n;
int height[NMAX];
long long code[NMAX];

int extract()
{
    int minn;
    if (q1.empty()) { minn = q2.front(); q2.pop();}
    else if (q2.empty()) { minn = q1.front(); q1.pop();}
    else {
        if (H[q1.front()].key <= H[q2.front()].key) { minn = q1.front(); q1.pop(); }
        else { minn = q2.front(); q2.pop(); }
    }
    return minn;
}

void dfs(int start)
{
    st.push(start);
    mark.set(start);
    mark.set(0);
    int y, target, ok;
    long long int cod = 0;
    int right = 0;
    while (!st.empty())
    {
        y = st.top();
        ok = 0;
        right = 0;
        if (H[y].left == 0 && H[y].right == 0)
        {
            height[y] = st.size() - 1;
            code[y] = cod;
        }
        else
        {
            if (!mark.test(H[y].left))
            {
                target = H[y].left;
                ok = 1;
            }
            else
                if (!mark.test(H[y].right))
                {
                    target = H[y].right;
                    ok = 1;
                    right = 1;
                }
        }
        if (ok)
        {
            st.push(target);
            mark.set(target);
            cod <<= 1;
            if (right)
                cod += 1;
        }
        else
        {
            st.pop();
            cod >>= 1;
        }
    }
}

node build_node(long long int key, int st, int dr)
{
    node aux;
    aux.key = key;
    aux.left = st;
    aux.right = dr;
    return aux;
}

int main()
{
    Read(n);
    int x;
    for (int i = 1; i <= n; i++)
    {
        Read(x);
        H[i] = build_node(x, 0, 0);
        q1.push(i);
    }
    in.close();
    int next_ord = n;
    if (n == 1)
    {
        out << 1 << "\n" << 0 << " " << 0 << "\n";
        return 0;
    }
    int min1, min2;
    min1 = q1.front();
    q1.pop();
    min2 = q1.front();
    q1.pop();
    H[++next_ord] = build_node(H[min1].key + H[min2].key, min1, min2);
    q2.push(next_ord);
    long long int total = (long long) H[q2.front()].key;
    for (int i = 1; i <= n - 2; i++)
    {
        min1 = extract();
        min2 = extract();
        H[++next_ord] = build_node(H[min1].key + H[min2].key, min1, min2);
        total += (H[min1].key + H[min2].key);
        q2.push(next_ord);
    }
    out << total << "\n";
    dfs(q2.front());
    for (int i = 1; i <= n; i++)
       out << height[i] << " " << code[i] << "\n";
    out.close();
    return 0;
}