#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") 

#include <iostream>
#include <fstream>
#include <queue>
#include <string>

using namespace std;

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

queue<pair<int, int>> nodeQ;
queue<pair<int, int>> mergedQ;
int adjList[2000002][2];
int nodeValues[1000000];
long long nodeEncodes[1000000];
long long sum;

void df(int currentNode, int encode, int depth) {
    if (adjList[currentNode][0] != 0) {
        df(adjList[currentNode][0] - 1, encode * 2, depth + 1);
    }
    if (adjList[currentNode][1] != 0) {
        df(adjList[currentNode][1] - 1, encode * 2 + 1, depth + 1);
    }

    if ((adjList[currentNode][0] == 0) && (adjList[currentNode][1] == 0)) { // If leaf
        sum += nodeValues[currentNode] * depth;
        nodeValues[currentNode] = depth; // Overwrite with depth
        nodeEncodes[currentNode] = encode;
        //cout << depth << ' ' << encode << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

    int n, index = 0;
    myIn >> n;
    for (int i = 0; i < n; ++i) {
        myIn >> nodeValues[i];
        nodeQ.push({ index,nodeValues[i] });
        ++index;
    }

    while ((nodeQ.empty() && mergedQ.size() == 1) == false) {
        pair<int, int> a = { -1,-1 };
        pair<int, int> b = { -1,-1 };

        for (int i = 0; i < 2; ++i) {
            pair<int, int>* elem = (i == 0) ? &a : &b;
            if (nodeQ.empty()) {
                //Extract from mergedQ 2 elements
                elem->first = mergedQ.front().first;
                elem->second = mergedQ.front().second;
                mergedQ.pop();
            }
            else if (mergedQ.empty()) {
                //Extract from nodeQ 2 elements
                elem->first = nodeQ.front().first;
                elem->second = nodeQ.front().second;
                nodeQ.pop();
            }
            else {
                //Extract 2 elements from both Q
                if (mergedQ.front().second > nodeQ.front().second) {
                    elem->first = nodeQ.front().first;
                    elem->second = nodeQ.front().second;
                    nodeQ.pop();
                }
                else {
                    elem->first = mergedQ.front().first;
                    elem->second = mergedQ.front().second;
                    mergedQ.pop();
                }
            }
        }

        //Merging
        adjList[index][0] = b.first + 1;
        adjList[index][1] = a.first + 1;
        pair<int, int> c = { index,a.second + b.second };

        ++index;
        mergedQ.push(c);
    };
    //cout << mergedQ.size() << ' ' << mergedQ.front().first << ' ' << mergedQ.front().second << '\n';

    df(index - 1, 0, 0);
    
    myOut << sum << '\n';
    for (int i = 0; i < n; ++i) {
        myOut << nodeValues[i] << ' ' << nodeEncodes[i] << '\n';
    }
}