#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{
    int ord;
    long long int key;
    node* left;
    node* 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 <node*> q1, q2;
bitset <2 * NMAX> mark;
stack <int> st;
node* H[2 * NMAX];
int n;
int height[NMAX], code[NMAX];

node* build_node(long long int x, node* left, node* right, int ord)
{
    node* aux = new node;
    aux -> key = x;
    aux -> left = left;
    aux -> right = right;
    aux -> ord = ord;
    return aux;
}

node* extract()
{
    node* minn;
    if (q1.empty()) { minn = q2.front(); q2.pop();}
    else if (q2.empty()) { minn = q1.front(); q1.pop();}
    else {
        if (q1.front() -> key <= 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);
    int y, target, ok;
    int cod = 0, right = 0;
    while (!st.empty())
    {
        y = st.top();
        ok = 0;
        right = 0;
        if (H[y] -> left != NULL && !mark.test(H[y] -> left -> ord))
        {
            target = H[y] -> left -> ord;
            ok = 1;
        }
        else
            if (H[y] -> right != NULL && !mark.test(H[y] -> right -> ord))
            {
                target = H[y] -> right -> ord;
                ok = 1;
                right = 1;
            }
            else
                if (H[y] -> left == NULL && H[y] -> right == NULL)
                {
                    height[y] = st.size() - 1;
                    code[y] = cod;
                }
        if (ok)
        {
            st.push(target);
            mark.set(target);
            cod <<= 1;
            if (right)
                cod += 1;
        }
        else
        {
            st.pop();
            cod >>= 1;
        }
    }
}

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