#include <stdio.h> 
#include <stdlib.h>

#define NUM_INPUTS 5000

/* Function prototypes: */ 
void Select_quantiles(int, int, int); 
int Select(int[], int, int, int); 
int Partition(int[], int, int, int); 
void Store(int, int); 
void read_integers(FILE*, int, int*); 
void print_integers(int*, int, FILE*); 
void Insertion_sort(int[], int, int); 
int find_med(int[], int, int); 

/* Global variable to track the number of comparisons */ 
int comp_count = 0; 

/*Global array to store the input numbers */ 
int input_array[NUM_INPUTS + 1]; 

/*Global pointer to storage space for output: k-1 elements*/ 
int *output_ptr; 

/*Global variable to store input value of k - number of quantiles to form
*/ 
int input_k; 


/* MAIN function.  Reads in a number of integer inputs, a value for the 
         number of quantiles, and locates the elements that divide the
input into 
         that many quantiles.  */ 
int  main(int argc, char** argv)
{ 
        /* Read NUM_INPUTS integers from stdin to input_array */ 
        read_integers(stdin, NUM_INPUTS, input_array);    

        /* Read in input_k - the number of quantiles to form */  
        fscanf(stdin, "%d", &input_k); 

        /*Allocate array to store the k-1 elements that form the kth
quantiles*/ 
        output_ptr = (int *) malloc((input_k-1)*sizeof(int)); 

        /* Locate the elements which form the quantiles.  Error check on
input_k 
                 first. */ 
        if ((input_k == 1) || (input_k >= NUM_INPUTS))  
        { 
                fprintf(stdout, "Illegal value for k = number of
quantiles. \n"); 
                exit(0); 
        }
        else  
                Select_quantiles(1, NUM_INPUTS, input_k-1);     

        /* Output the quantile markers and the number of comparisons it
took to 
                 find them. */  
        print_integers(output_ptr, input_k-1, stdout);          
        fprintf(stdout, "%d\n", comp_count); 

        return(0); /*success*/ 
}/*end: main()*/ 


/* Function to identify elements within a section of an array which mark 
         quantile boundaries for the elements of that section.  p is the
index of 
         the first element in the section.  q is the index of the last
element in 
         the section.  num_quantiles is the number of quantile markers to 
         identify.  */ 
void Select_quantiles(int p, int q, int num_quantiles)
{ 
        int median_quantile = 0; 
        int num_quantiles1 = 0; 
        int num_quantiles2 = 0; 
        int section_length = q - p + 1; 
        int c; 
        int index; 
 
        if ((num_quantiles % 2) != 0) 
        { /* num_quantiles is odd */   

                /* Find the rank (p-based) of the median quantile marker
*/  
                median_quantile =  (section_length / 2); 
                        
                /* All but this median will be found recursively.
Calculate how 
                         many quantile markers are to the left and to the
right of the median 
                         quantile marker. Because num_quantiles is odd,
there is one median 
                         with an equal number of quantile markers to
wither side of it. */ 
                num_quantiles1 = num_quantiles2 = (num_quantiles - 1) / 2; 
                
        }/*endif: num_quantiles is odd*/  
        else 
        { /* num_quantiles is even */  
                        
                /* Find the rank (p-based) of the lower of the two median
quantiles */  
                median_quantile =  ((num_quantiles * section_length) / 

(2 * (num_quantiles + 1))); 

                /* Calculate how many quantiles are to be found in each
recursive call. 
                         There will be one less in the left portion than
in the right portion. */ 
                num_quantiles1 =  ((num_quantiles-1)/2); 
                num_quantiles2 = num_quantiles - num_quantiles1 - 1; 
        
        }/*endelse: num_quantiles is even*/  

        /* Call Select to find the element with rank median_quantile.
Note 
                 median_quantile is a p-based rank */ 
        c = Select(input_array, p, q, median_quantile); 

        /* Store the quantile to the output array, in order*/ 
        index = (p + median_quantile) * input_k / NUM_INPUTS - 1;       
        Store(c, index); 

        /* Recursive calls to find the other quantile markers, if there
are others 
                 to find. */ 
        if (num_quantiles > 2) 
                Select_quantiles(p, p+median_quantile - 1,
num_quantiles1); 

        if (num_quantiles > 1) 
                Select_quantiles(p+median_quantile, q, num_quantiles2); 

}/*end: Select_quantiles() */  


/* Function to select an element of a certain rank from a section of an
array. 
         p is the index of the first element of the section.  q is the
index of the 
         last element of the section.  target is the rank of the element
being 
         selected.  target must be provided as a p-based index.  So, if
target is 
         1, the element that belongs in array[p] will be returned.  If
target is 
         q-p+1, the element which belongs in array[q] will be returned.
Note 
         that this is a deterministic algorithm.  */   
int Select(int array[], int p, int q, int target) 
{ 
        int section_length = q - p + 1; 
        int epg = 11; /*elements per group*/  
        int num_groups = section_length / epg; 
        int i; 
        int remains;  
        int median_array[num_groups + 1]; /* May be an extra slot, or just
right */  
        int med, med_of_meds, rank_of_med; 
        int part_index; 

        /* Check whether this section has more than one element.  If not,
return 
     that element (after error-checking that target is indeed 1). */ 
        if (p == q) 
        { 
                if (target == 1) 
                        return(array[p]); 
                else 
                { 
                        fprintf(stderr, "Select called with single
element, target != 1\n"); 
                        exit(0); 
                } 
        }/*endif: only one element in the section */  

        /* Error check: target should be less than the number of elements
in this 
          section. */ 
        if (target > section_length) 
        { 
                fprintf(stderr, "Select called with target beyond
max_index\n"); 
                exit(0); 
        }/*endif: target exceeds number of elements*/  

        /* Divide the elements into groups of size epg, and store the
median of 
                 each group into median_array.  Nothing fancy about the
grouping; just 
                 take the first epg elements, then the next epg elements,
and so on. */         
        for(i=0; i<num_groups; i++) 
        { /* Find median of the next epg elements */ 
                med = find_med(array, epg*i +p, epg*i+4+p);             
                /* Store med in a temporary array */ 
                median_array[i] = med; 
        }/* end for loop through complete groups*/  
 
        /* If there were elements left over, process them now as a partial
group */ 
        remains = section_length % epg; 
        if (remains != 0) 
        { 
                num_groups ++; 
                med = find_med(array, q-remains+1, q); 
                /* Add med to the temporary array */
                median_array[num_groups-1] = med; 
        }/*endif: not evenly divisible */ 

        /* Next find the median of the medians from each group.  If there
is a 
                 small number of medians (<=epg), find the median by
sorting and  
     extracting the proper element.  If there is a large number of groups, 
                 call select recursively to find the median. */  
        if (num_groups <= epg) 
        { /*find median of medians directly*/  
                med_of_meds = find_med(median_array, 0, num_groups-1); 
        } 
        else 
        {  
                /* Call Select on the array of medians to find the median
of the medians */ 
                rank_of_med = (int)(num_groups/2.0 + 0.5); /* ceiling of
(num_groups/2) */  
                med_of_meds = Select(median_array, 0, num_groups-1,
rank_of_med);  
        } 

        /* Partition this section of the array about the median of medians
*/ 
        part_index = Partition(array, p, q, med_of_meds);       

        /* Unless part_index is the rank we want, call select recursively
on 
                 whichever portion target is in. */  
        if (target == part_index) 
                return array[p+part_index-1]; 
        else if (target < part_index) 
                return Select(array, p, p+part_index-2, target); 
        else /*target > part_index*/ 
                return Select(array, p+part_index, q, target-part_index ); 
  
}/*end: Select() */ 


/* Function to partition a section of an array about a given value.  
         p is the index of the first element in the section.  q is the
index 
         of the last element in the section. Partition returns the index j 
         of an element of the given value.  All elements before j in this
section 
         will be less than or equal to value.  All elements after j will
be 
         greater than or equal to value.  

         j will be returned as a p-based index.  So j=1 means the element
at 
         position p was the pivot.  j=q-p+1 means the element at position
q 
         was the pivot.     
*/ 
int Partition(int array[], int p, int q, int value) 
{ 
        int x, temp, index; 
        int i, j, k; 

        x = value; 
        i = p; 
        j = q; 

        while(1) 
        { 
                /*Scan down from top, looking for first element <= x*/ 
                while(array[j] > x) 
                { 
                        comp_count++; /* increment comparison count */  
                        j--;    
                }/*end: while loop scanning down */  

                /* Add one more comparison for the failed while loop
compare */ 
                comp_count++; 
 
                /*Scan up from bottom, looking for first element > x */ 
                while(array[i] <= x) 
                { 
                        comp_count++; /*increment comparison count*/  
                        i++; 
                }/*end: while loop scanning up*/ 

                /* Add one more comparison for the failed while loop
compare */ 
                comp_count++; 
  
                /* If the two scanning pointers have not crossed, swap the
elements they 
                   point to.  If they have crossed, stop scanning. */  
                if (i<j) 
                { 
                        /* swap elements*/       
                        temp = array[i]; 
                        array[i] = array[j]; 
                        array[j] = temp; 
                }  
                else 
                        break; 

        }/*end: while loop to scan in from ends, swapping elements */ 

        /* All elements between p and j, inclusive, are less than or equal
to value. 
           But we want the element at j to equal value.  So scan from the
start till 
                 we find it, and swap that element with the element
currently at position 
                 j.  Then convert j to a p-based index and return.  */ 
        index = p; 
        while (index<=q) 
        {
                comp_count++; /*increment comparison count*/   
                if (array[index] == value) 
                { /*Swap this element with the element at j*/ 
                        temp = array[index]; 
                        array[index] = array[j]; 
                        array[j] = temp; 
                        /*return j, as a p-based index */  
                        return j-p+1;   
                } 
                index++;  
        }//end: while loop to move partition element to index j

}/*end: Partition() */  


/* Function to find the median of a section of array.  It uses insertion
sort 
   to sort the array, then returns the median element.  If there are two 
   medians, it returns the lower of the two.  Because insertion sort is
used, 
   this is best for small array sections.  p is the index of the first 
         element in the section.  q is the index of the last element of
the section.
*/  
int find_med(int array[], int p, int q) 
{ 
        int section_length = q - p + 1; 
        Insertion_sort(array, p, q); 

        /* Note this returns the lower median, if section_length is even
*/ 
        return array[(section_length/2) + p];           

}/*end: find_med()*/ 


/* Function to sort a section of an array using insertion sort.  p is 
         index of the first element of the section.  q is the index of the
last 
   element of the section.  This takes worst-case Theta-n-squared time, so
is 
   best for small sections of arrays only. 
*/   
void Insertion_sort(int array[], int p, int q)  
{ 
        int j, i, key; 
        int section_length = q - p + 1; 

        for(j=p+1; j<=q; j++) 
        { 
                key = array[j]; 
                i = j-1; 
                while ((i >= p) && (array[i] > key))   
                { 
                        comp_count++;  
                        array[i+1] = array[i]; 
                        i = i-1; 
                } 
                comp_count++; /*Add one for failed while compare */  
 
                array[i+1] = key; 
        } 

}/*end: Insertion_sort()*/ 


/* Function to store an element to a certain index of the output data.  
   Called by Select_quantiles to store quantile markers (in order) for
output. 
*/ 
void Store(int element, int index)
{ 
        if (index > input_k-1) 
        { 
                printf("Error: Store called with index out of bounds!\n"); 
                exit(0); 
        } 
 
        *(output_ptr+index) = element; 
}/*end: Store()*/ 


/* Function to read a certain number of integer inputs from a given 
   source, and store them to a given destination.  For this program, 
   this is used to read in the NUM_INPUTS integers from stdin and 
         store them to input_array. Note no error checking is done!  It 
         assumes that a user will enter the expected inputs.    
*/  
void read_integers(FILE *source, int num_inputs, int *destination ) 
{ 
        int i; 

        for(i=0; i<num_inputs; i++)  
                fscanf(source, "%d", destination+i); 

}/*end: read_integers()*/ 


/* Function to print a given number of integers, from a specified source 
         to a specified destination.  Note no error-checking is done.  For
this 
         program, this is used to print the quantile markers from
output_array 
         to stdout.  Note no error checking is done! 
*/ 
void print_integers(int *source, int num_outputs, FILE *destination) 
{ 
        int i; 

        for(i=0; i< num_outputs; i++) 
                fprintf(destination, "%d\n", *(source+i)); 

}/*end: print_integers()*/