#include <iostream>
#include <vector>
#include <queue>
#include <bits/stdc++.h>
#include <map>

using namespace std;
using ll = long long;
const int nmax = 1e6 + 9;
ll freq[nmax];
int n;

struct node {
    
    ll sum;
    node* child[2];
    int fin;
};
queue<node*> q1, q2;

node* getNext ()
{
    node* ret;
    if (q1.empty()) {
        ret = q2.front();
        q2.pop();
    }
    else if (q2.empty())
    {
        ret = q1.front();
        q1.pop();
    }
    else if (q1.front()->sum < q2.front()->sum)
    {
        ret = q1.front();
        q1.pop();
    }
    else {
        ret = q2.front();
        q2.pop();
    }
    return ret;
}

node* build ()
{
    for (int i = 1; i <= n; i++)
    {
        q1.push(new node{freq[i], {0,0}, i});
    }
   while (q1.size() + q2.size() > 1)
    {
        node* n1 = getNext();
        node* n2 = getNext();
        q2.push(new node({n1->sum + n2->sum, {n1, n2}, 0}));
    }
    return q2.front();
}

node* root;
ll codes[nmax];
ll length[nmax];
void findCodes (node* nod = root, ll cod = 0, ll bit = 0)
{
    if (nod->fin != 0) {
        length[nod->fin] = bit;
        codes[nod->fin] = cod;
        return;
    }
    findCodes(nod->child[0], cod << 1ll, bit + 1ll);
    findCodes(nod->child[1], (cod << 1ll) + 1ll, bit + 1ll);
}

int main ()
{
    freopen("huffman.in" , "r" , stdin);
    freopen("huffman.out" , "w" , stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n; 
    for (int i = 1; i <= n; i++)
    {
        cin >> freq[i];
    }
    root = build();
    findCodes();
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        
        sum += length[i] * freq[i];
    }
    cout << sum << '\n';
    for (int i = 1; i <= n; i++)
    {
        cout << length[i] << ' ' << codes[i] << '\n';
        
    }
}