#include<fstream>
#define DIM 2000001
using namespace std;
ifstream fin("huffman.in");
ofstream fout("huffman.out");
long long cod[DIM],w[DIM];
int nr[DIM],st[DIM],dr[DIM];
int n,i,x,a,b,k,p1,p2;
long long sol;
int next_el()
{
int a=-1,b=-1,ca=0,cb=0;
if(p2<k) b=p2;
if(p1<=n) a=p1;
if(a==-1) cb=1;
else if(b==-1) ca=1;
else if(w[a]>w[b]) cb=1; else ca=1;
if(ca==1)
{
p1++;
return a;
}
p2++;
return b;
}
void solve(int nod,int nivel)
{
nr[nod]=nivel;
long long aux=cod[nod];
if(st[nod]!=0)
{
sol+=w[nod];
cod[st[nod]]=aux*2,cod[dr[nod]]=aux*2+1;
solve(st[nod],nivel+1);
solve(dr[nod],nivel+1);
}
}
int main()
{
fin>>n;
for(i=1;i<=n;i++){
fin>>x;
w[i]=x;
}
p1=1;p2=n+1;
for(k=n+1;;k++)
{
a=next_el();b=next_el();
w[k]=w[a]+w[b];
st[k]=a;dr[k]=b;
if(p1==n+1&&p2==k) break;
}
solve(k,0);
fout<<sol<<"\n";
for(i=1;i<=n;i++) fout<<nr[i]<<" "<<cod[i]<<"\n";
return 0;
}