#include <iostream>
#include<fstream>
#include<vector>
using namespace std;

ifstream in("huffman.in");
ofstream out("huffman.out");
int frecv[1000000],nodes;

struct path_info
{
    int formed;
    int path_length;
};

path_info paths[1000000];//how we get to the huffman node


struct node
{
public:
    const int index;
    const int cost;

    node*left;
    node*right;

    node(int in,int co):index(in),cost(co)
    {
        left=nullptr;
        right=nullptr;
    }

};
vector<node*> huffman_tree;
node*huffman_root;

void read()
{
    in>>nodes;
    for(int i=0; i<nodes; i++)
    {
        in>>frecv[i];
    }

}



void get_first(node*&a,node*&b)
{
    int m=99999999;
    int index;
    for(int i=0; i<huffman_tree.size(); i++)
    {
        node*here=huffman_tree[i];
        if(here->cost<m)
        {
            a=here;
            m=here->cost;
            index=i;
        }
    }//first node
    huffman_tree.erase(huffman_tree.begin()+index);

    m=99999999;
    for(int i=0; i<huffman_tree.size(); i++)
    {
        node*here=huffman_tree[i];
        if(here->cost<m)
        {
            b=here;
            m=here->cost;
            index=i;
        }
    }//first node
    huffman_tree.erase(huffman_tree.begin()+index);

}


void prt_huffman()
{
    for(int i=0; i<huffman_tree.size(); i++)
        cout<<huffman_tree[i]->cost<<" ";
    cout<<endl;

}

void create_huffman()
{
    for(int i=0; i<nodes; i++)
    {
        node*newnode=new node(i,frecv[i]);
        huffman_tree.push_back(newnode);
    }
    int index=nodes;


    while(huffman_tree.size()>1)
    {

        node*a,*b;
        get_first(a,b);

        node*new_root=new node(index,a->cost+b->cost);
        new_root->left=a;
        new_root->right=b;

        index++;
        huffman_tree.push_back(new_root);

    }
    huffman_root=huffman_tree[0];

}
int sum=0;
void set_nodes(node*root,int formed,int pth)
{
    if(root->left==nullptr && root->right==nullptr)
    {
        sum+=pth*frecv[root->index];
        paths[root->index].formed=formed;
        paths[root->index].path_length=pth;
    }
    else
    {
        if(root->left)
        {
            set_nodes(root->left,formed<<1,pth+1);
        }
        if(root->right)
        {
            set_nodes(root->right,(formed<<1)+1,pth+1);
        }

    }

}


void prt_result()
{
    out<<sum<<'\n';
    for(int i=0; i<nodes; i++)
    {
        out<<paths[i].path_length<<" "<<paths[i].formed<<'\n';
    }



}


int main()
{
    read();
    create_huffman();
    set_nodes(huffman_root,0,0);
    cout<<"total len "<<sum<<endl;
    prt_result();
    return 0;
}