#include <fstream>
#include <cstring>
using namespace std;

const int N = 1 + 1e6;
const long long inf = 0x3f3f3f3f3f3f3f3f;

struct Simbol{
    int label;
    long long frecv;

    Simbol() : label(0), frecv(0) {};
    Simbol(int label, long long frecv) : label(label), frecv(frecv) {};
};

class Queue{
    Simbol v[N];
    int st, dr;

public:
    Queue() : st(0), dr(0) {};

    inline void push( int label, int frecv ){
        v[dr++] = Simbol(label, frecv);
    }

    inline long long getTopFrecv(){
        return st != dr ? v[st].frecv : inf;
    }

    inline Simbol pop(){
        return v[st++];
    }

    inline int size(){
        return dr - st;
    }
};

Queue A, B;
long long cod[2 * N], frecv[2 * N];
int T[2 * N], bitSize[2 * N], n;
bool bit[2 * N];

inline Simbol getBest(){
    return A.getTopFrecv() < B.getTopFrecv() ? A.pop() : B.pop();
}

int main(){
    ifstream in("huffman.in");
    in >> n;
    for (int i = 1 ; i <= n ; i++){
        in >> frecv[i];
        A.push(i, frecv[i]);
    }
    in.close();

    int nr = n;
    Simbol a, b;
    while (1 < A.size() + B.size()){
        a = getBest();
        b = getBest();
        T[ a.label ] = T[ b.label ] = ++nr;
        B.push( nr, a.frecv + b.frecv );
    }

    cod[nr] = bitSize[nr] = 0;
    for (int i = nr - 1 ; i ; i--){
        bitSize[i] = 1 + bitSize[ T[i] ];
        cod[i] = ( cod[ T[i] ] << 1 ) ^ bit[ T[i] ];
        bit[ T[i] ] ^= 1;
    }

    long long cost = 0;
    for (int i = 1 ; i <= n ; i++)
        cost += frecv[i] * bitSize[i];

    ofstream out("huffman.out");
    out << cost << '\n';
    for (int i = 1 ; i <= n ; i++)
        out << bitSize[i] << ' ' << cod[i] << '\n';
    out.close();

    return 0;
}