#include <fstream>
#include <queue>
#define maxn 1000100
struct Node
{
long long freq;
int l, r;
Node(long long a) : freq(a), l(-1), r(-1) {}
Node(long long a, int b, int c) : freq(a), l(b), r(c) {}
};
long long myP[maxn][2];
int extract(std::queue<int> &A, std::queue<int> &B, std::vector<Node> &myV);
void dfs(int nod, std::vector<Node> &myV, long long &sum, int s, long long d);
int main()
{
std::ifstream in("huffman.in");
std::ofstream out("huffman.out");
int nV;
long long nr;
in >> nV;
std::vector<Node> myV;
std::queue<int> myQ1, myQ2;
for(int i = 0; i < nV; i++)
in >> nr, myQ1.push(i), myV.push_back(Node(nr));
int a, b;
while(true)
{
a = extract(myQ1, myQ2, myV);
b = extract(myQ1, myQ2, myV);
if(b == -1)
break;
else
{
myV.push_back(Node(myV[a].freq + myV[b].freq, a, b));
myQ2.push(myV.size() - 1);
}
}
nr = 0;
dfs(a, myV, nr, 0, 0);
out << nr << '\n';
for(int i = 0; i < nV; i++)
out << myP[i][0] << ' ' << myP[i][1] << '\n';
return 0;
}
void dfs(int nod, std::vector<Node> &myV, long long &sum, int s, long long d)
{
if(myV[nod].l == myV[nod].r)
{
myP[nod][0] = s;
myP[nod][1] = d;
}
else
{
sum += myV[nod].freq;
dfs(myV[nod].l, myV, sum, s + 1, d * 2);
dfs(myV[nod].r, myV, sum, s + 1, d * 2 + 1);
}
}
int extract(std::queue<int> &A, std::queue<int> &B, std::vector<Node> &myV)
{
int a = 0;
if(A.empty() && B.empty())
return -1;
else if(A.empty())
{
a = B.front();
B.pop();
return a;
}
else if(B.empty())
{
a = A.front();
A.pop();
return a;
}
else if(myV[A.front()].freq < myV[B.front()].freq)
{
a = A.front();
A.pop();
return a;
}
else
{
a = B.front();
B.pop();
return a;
}
}