class IndirectHeap {
    int[] elements;
    int[] positions;
    int n;
    
    IndirectHeap(int[] as, int size) 
    /*@IndirectHeap_pre@*/
    {
	elements = as;
	elements[0] = -1; 
	n = size ;
	positions = new int[n+1];
	for(int i = 0; i <= n; i++)
	    positions[i] = i;
	for(int i = n ; i > 0; i--)
	    downHeap(i);
    }
    /*@IndirectHeap_post@*/

    int size() 
    /*@size_pre@*/
    {
	return n;
    }
    /*@size_post@*/

    int remove() 
    /*@remove_pre@*/
    {
	int h = positions[1];
	positions[1] = positions[n--];
	downHeap(1);
	return h;
    }
    /*@remove_post@*/

    int top() 
    /*@top_pre@*/
    {
	return positions[1];
    }
    /*@top_post@*/

    void replaceTop(int newIndex) 
    /*@replaceTop_pre@*/
    {
	positions[1] = newIndex;
	downHeap(1);
    }
    /*@replaceTop_post@*/

    void downHeap(int i) 
    /*@downHeap_pre@*/
    {
	int v = positions[i];
	int nhalf = n / 2;
	while (i <= nhalf) {
	    int j = 2 * i;
	    if( (j < n) && (elements[positions[j]] < elements[positions[j+1]])) 
//	    if( (j < n) && (elements[positions[j]] > elements[positions[j+1]])) 
		j++;
	    if (elements[v] <= elements[positions[j]]) 
		nhalf = -1; /* terminate loop */
	    else {
		positions[i] = positions[j];
		i = j;
	    }
	}
	positions[i] = v;
    }
    /*@downHeap_post@*/
}

class Huffman {
    static int[] buildTree(int[] counts) 
    /*@buildTree_pre@*/
    {

       	int n = counts.length;

	int[] charCount = new int[2 * n];
	int parent[] = new int[2 * n];

	for (int i = 0; i < n; i++)
	    charCount[i+1] = counts[i];

	IndirectHeap heap = new IndirectHeap(charCount, n);
	
	while(heap.size() > 1) {
	    int top = heap.remove();
	    int top2 = heap.top();
	    charCount[++n] = charCount[top] + charCount[top2];
	    parent[top] = n;
	    parent[top2] = -n;
	    heap.replaceTop(n);
	}
	parent[n]=0;

	return parent;
    }
    /*@buildTree_post@*/
    
    static int[] demo(int c1, int c2, int c3, int c4, int c5, int c6, int c7) 
    /*@demo_pre@*/
    {
	int[] counts =  new int[7];
	counts[0] = c1;
	counts[1] = c2;
	counts[2] = c3;
	counts[3] = c4;
	counts[4] = c5;
	counts[5] = c6;
	counts[6] = c7;
	int[] parents = buildTree(counts);
	return parents;
    }
    /*@demo_post@*/
}