#include <iostream>
#include<fstream>
#include<deque>
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 cost;
    const int index;
    node*left;
    node*right;

    node(int co,int id):cost(co),index(id)
    {
        left=nullptr;
        right=nullptr;
    }
    node(node*l,node*r):cost(l->cost+r->cost),index(0)
    {
        left=l;
        right=r;
    }

};
node*huffman_root;

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

}

deque<node*> original_nodes;
deque<node*>intermediate_nodes;


void prt_hff()
{
    cout<<"original nodes"<<endl;
    for(int i=0; i<original_nodes.size(); i++)
        cout<<original_nodes[i]->cost<<" ";
    cout<<endl<<"intermediate nodes"<<endl;
    for(int i=0; i<intermediate_nodes.size(); i++)
        cout<<intermediate_nodes[i]->cost<<" ";
    cout<<endl;
}


void create_huffman()
{



    //we create all original nodes
    for(int i=0; i<nodes; i++)
    {
        node*newnode=new node(frecv[i],i);
        original_nodes.push_back(newnode);
    }
    //prt_hff();


    while(original_nodes.size() || intermediate_nodes.size()>1)
    {


        if(intermediate_nodes.size()==0)
        {
            node*n=new node(original_nodes[0],original_nodes[1]);
            original_nodes.pop_front();
            original_nodes.pop_front();
            intermediate_nodes.push_back(n);
        }
        else if(original_nodes.size()==0)
        {
            node*n=new node(intermediate_nodes[0],intermediate_nodes[1]);
            intermediate_nodes.pop_front();
            intermediate_nodes.pop_front();
            intermediate_nodes.push_back(n);
        }
        else
        {
            if(original_nodes[0]->cost<intermediate_nodes[0]->cost)
            {
                int next=9999999;
                if(original_nodes.size()>1)
                    next=original_nodes[1]->cost;

                if(next<intermediate_nodes[0]->cost)
                {
                    node*n=new node(original_nodes[0],original_nodes[1]);
                    original_nodes.pop_front();
                    original_nodes.pop_front();
                    intermediate_nodes.push_back(n);
                }
                else
                {
                    node*n=new node(original_nodes[0],intermediate_nodes[0]);
                    original_nodes.pop_front();
                    intermediate_nodes.pop_front();
                    intermediate_nodes.push_back(n);
                }
            }
            else
            {

                int next=9999999;
                if(intermediate_nodes.size()>1)
                    next=intermediate_nodes[1]->cost;

                if(next<original_nodes[0]->cost)
                {
                    node*n=new node(intermediate_nodes[0],intermediate_nodes[1]);
                    intermediate_nodes.pop_front();
                    intermediate_nodes.pop_front();
                    intermediate_nodes.push_back(n);
                }
                else
                {
                    node*n=new node(original_nodes[0],intermediate_nodes[0]);
                    original_nodes.pop_front();
                    intermediate_nodes.pop_front();
                    intermediate_nodes.push_back(n);
                }

            }

        }

       // prt_hff();
    }

    huffman_root=intermediate_nodes[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;
}