#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma warning(disable:4996)
using namespace std;
long long s;
struct data
{
    int nr;
    long long len;
}auxi;
struct Nod
{
    int nr_ord;  //numarul de ordine (primul/al doilea/ al n-lea elem)
    int fr;      // frecv
    Nod* left;
    Nod* right;
};
data rez[1000005];
long long get_nr(string alfa)
{
    long long ans = 0;
    for(auto it : alfa)
    {
        if(it == '0') ans = ans * 2;
        if(it == '1') ans = ans * 2 + 1;
    }
    return ans;
}
void span(Nod *& node, string & a)
{
    if(node -> nr_ord != 0)
    {
        s = s + a.size() * node -> fr;
        auxi.len = a.size();
        auxi.nr = get_nr(a);
        rez[node -> nr_ord] = auxi;
    }
    if(node -> right != NULL)
    {
        a = a + "1";
        span(node -> right, a);
        a.pop_back();
    }
    if(node -> left != NULL)
    {
        a = a + "0";
        span(node -> left, a);
        a.pop_back();
    }
}
deque <Nod*> Q1, Q2;
long long i, n, x;
Nod *root, *aux, *aux1, *aux2, *nil = NULL;
string a;
Nod* extract_front()
{
    Nod *A, *B;
    if(Q1.empty() && Q2.empty())return nil;
    if(Q1.empty())
    {
        A = Q2.front();
        Q2.pop_front();
        return A;
    }
    if(Q2.empty())
    {
        B = Q1.front();
        Q1.pop_front();
        return B;
    }
    A = Q1.front();
    B = Q2.front();
    if(A -> fr < B -> fr)
    {
        Q1.pop_front();
        return A;
    }
    Q2.pop_front();
    return B;
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ifstream f("huffman.in");
    ofstream g("huffman.out");
    f >> n;
    for(i = 1; i <= n; i ++)
    {
        f >> x;
        aux = new Nod;
        aux -> left = NULL;
        aux -> right = NULL;
        aux -> fr = x;
        aux -> nr_ord = i;
        Q1.push_back(aux);
    }
    while(!Q1.empty() || !Q2.empty())
    {
        aux =  extract_front();
        aux1 = extract_front();
        if(aux1 == NULL)break;
        root = new Nod;
        root -> nr_ord = 0;
        root -> fr = aux -> fr + aux1 -> fr;
        root -> left = aux;
        root -> right = aux1;
        Q2.push_back(root);
    }
    root = aux;
    span(root, a);
    g << s << "\n";
    for(i = 1; i <= n; i ++)
        g << rez[i].len << " " << rez[i].nr << "\n";
    return 0;
}