//
//  tournament.c
//  
//
//  Created by Bibhas Ghoshal on 04/06/22.
//

#include <stdio.h>

void main()
{
    int tourn[100],i,n,min;
    
    /* Read N */
    
    printf("Give n:");
    scanf("%d",&n);
    printf("\n n = %d \n",n);
    
    for(i=n; i<=2*n-1; i++){
        scanf("%d",&tourn[i]);
    }
    /* Build the tournament */
        
    buildtourn(tourn,n);
    
    min = minval(tourn,n)-1;
    printf("\n min  = %d",min);
    
    /* Sorting */
    
    printf("\n Sorted items are : \n");
    
    for(i=1;i<=n; i++){
      printf("%d\t",tourn[1]);
      getnext(tourn,n,min);
    }
    printf("\n");
    
}


buildtourn(tourn,n)
int n,tourn[];
{
    int i;
    for(i=2*n-2;i>1; i=i-2){
        tourn[i/2] = maxi(tourn[i],tourn[i+1]);}
}
    
int getnext(tourn,n,min)
int tourn[],n,min;
{
    int i=2, next;
    
    /* Downward Traversal */
    
    while(i<= 2*n-1){
        
        if(tourn[i]>tourn[i+1]){
            tourn[i] = min;
            i = 2*i;
        }
        else{
            tourn[i+1] = min;
            i = 2*(i+1);
        }
        
    }

    /* Upward Recomputation */

    for(i=2*n-2;i>1; i=i-2){
        if(i%2==0)
            tourn[i/2]= maxi(tourn[i],tourn[i+1]);
        else
            tourn[i/2]= maxi(tourn[i],tourn[i-1]);
    }
}



int maxi(int a ,int b)
{
    if(a>b) return(a);
    else return(b);
}

int mini(int a ,int b)
{
    if(a<b) return(a);
    else return(b);
}

int minval(tourn,n)
int tourn[],n;
{
    int i,minimum;
    minimum = tourn[n];
    for(i=n;i<=2*n-1;i++){
        if(tourn[i]<minimum) minimum=tourn[i];
        
    }
    return minimum;
}