#include<cstdio>
const int N=1000001,M=15000000;
long long q[N];
int n,i,j,k,s[N],d[N],r[N],p[N],e=-1,l;
char u[M];
inline int B()
{
int s=0;
for(e++;u[e]>47;e++)
s=s*10+u[e]-48;
return s;
}
inline void S(long long x)
{
int i,j,e[20];
if(!x)
u[l++]=48;
for(j=0;x;x/=10)
e[j++]=x%10;
for(i=0;i<j;i++)
u[l+j-i-1]=e[i]+48;
l+=j;
}
inline void A(int k,long long a,int b)
{
if(k>n)
A(s[k-n],2*a,b+1),A(d[k-n],2*a+1,b+1);
else
p[k]=b,q[k]=a;
}
int main()
{
freopen("huffman.in","r",stdin),freopen("huffman.out","w",stdout),fread(u,1,M,stdin),n=B();
for(i=1;i<=n;i++)
q[i]=N,r[i]=B();
for(k=j=i=1;i<n;q[0]+=q[i++])
if(k<n&&r[k+1]<=q[j])
q[i]=r[k]+r[k+1],s[i]=k++,d[i]=k++;
else if(q[j+1]<=r[k]||k==n+1)
q[i]=q[j]+q[j+1],s[i]=n+j++,d[i]=n+j++;
else
q[i]=r[k]+q[j],s[i]=k++,d[i]=n+j++;
S(q[0]),u[l++]=10,A(2*n-1,0,0);
for(i=1;i<=n;i++)
S(p[i]),u[l++]=32,S(q[i]),u[l++]=10;
fwrite(u,1,l,stdout);
}