import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

/**
  John P. Cataldo &lt;cataldoj@ccs.neu.edu&gt;<br>
  Daniel Rinehart &lt;danielr@ccs.neu.edu&gt;<br>
  Aris Yannopoulos &lt;aris@ccs.neu.edu&gt;<br>
  COM1390 Programming Assignment #1<P>

  $Id: FindQuantiles.java,v 1.5 1999/02/16 21:20:29 danielr Exp $<P>

  Find the quantiles in a range.

  */
public class FindQuantiles {

  private static boolean debug = false;
  private static int comparisons = 0;

  /**

    This decides based on the size of the partition and the number of
    ranks in it wether or not we should sort the range or make
    recursive calls to findQuantiles.

    @param size the size of the partition we are dealing with
    @param numberOfRanks the number of ranks we are looking for in this range

    @return true if the range should be sorted; false otherwise

    */
  private static boolean shouldSort( int size, int numberOfRanks ) {
    // sizes larger than 20 should always be done via partitioning
    if ( size > 20 ) {
      return( false );
    }
    
    // always sort for sizes less than 8
    if ( size < 8 ) {
      return( true );
    }

    // better to use our smart biasedPartition
    if ( numberOfRanks <= 1 ) {
      return( false );
    }

    // do a little logic on the density of ranks in n
    double distrib = ( double )size / ( double )numberOfRanks;
    if ( distrib > 1.3 ) {
      return( true );
    }
    
    // otherwise partition it
    return( false );
  }

  /**

    Find all of the ranks specified in the given range.

    @param S the array of values to find the ranks for
    @param p the begin point of the range to consider
    @param r the end point of the range to consider
    @param K the array equal to length S marking the ranks to find
    
    */
  public static void findQuantiles( int[] S, int p, int r, int[] K ) {
    // the size of this section
    int size = ( r - p ) + 1;

    // ignore if the range length is 0 or 1 elements long
    if ( size <= 1 )
      return;

    // figire out how many ranks we are looking for in this range
    int numberOfRanks = 0;
    for( int index = p; index <= r; index++ ) {
      numberOfRanks += K[ index ];
    }

    // if this range doesn't have any ranks in it ignore it
    if ( numberOfRanks == 0 )
      return;

    // give the number of ranks we are looking for in the given size
    // it might be better just to sort the range
    // figure that out
    if ( shouldSort( size, numberOfRanks ) ) {
      if ( debug )
	System.err.println( "Calling MergeInsertion with " + size + " and " + numberOfRanks );
      MergeInsertion.sort( S, p, r );
    } else {
      // element to parition around
      int i = -1;

      // we try and be smart when we are looking for only one
      // element in a range 
      if ( numberOfRanks == 1 ) {
	i = FindRank.biasedPartition( S, p, r, K );
	if ( i != -1 && debug )
	  System.err.println( "FindRank gave us something." );
      }
      
      // if find rank doesn't think it can do something smart
      // just do a normal partition
      if ( i == -1 ) {
	// a good parition for a large sized section is very important
	// so use a large subset of the region
	// use a medium subset of a middle sized region
	// use just a random element when the size is very small
	if ( size > 40 ) {
	  i = Median.medianOf9Random( S, p, r );
	} else if ( size > 7 ) {
	  i = Median.medianOf3Random( S, p, r );
	} else {
	  i = p + ( int )( Math.random() * ( double )size );
	}
      }

      // we have picked the index to partition around do the partition
      int temp = S[ i ];
      S[ i ] = S[ r ];
      S[ r ] = temp;
      
      int q = Partition.partition( S, p, r );
      if ( debug )
	System.err.println( "Final q " + q + " over " + p + " to " + r );
      
      // recurse for each side
      findQuantiles( S, p, q - 1, K );
      findQuantiles( S, q + 1, r, K );
    } // partition instead of sort
  } 

  ////////////////////////////////////////////////////////////////
  // Comparision Callback Functions
  ////////////////////////////////////////////////////////////////

  /**

    Increase the total number of comparisions used.
    
    @param amount the amount to increase the number of comparisions by.

    */
  public static void incComp( int amount ) {
    comparisons += amount;
  }

  /**

    How many comparisions have been been used.

    @return the total number of comparisons used.
    
    */
  public static int totalComp() {
    return( comparisons );
  }

  /**
    
    Reset the numer of comparisions used to 0.

    */
  public static void resetComp() {
    comparisons = 0;
  }

  ////////////////////////////////////////////////////////////////
  // The Main Function
  ////////////////////////////////////////////////////////////////

  public static void main( String args[] ) {
    // we need to read 5000 ints from STDIN
    BufferedReader inputStream 
      = new BufferedReader( new InputStreamReader( System.in ) );
    
    int S[] = new int[ 5000 ];
    String line = "";

    // read in the 5000 ints
    for ( int i = 0; i < 5000; i++ ) {
      try {
	line = inputStream.readLine();
      } catch( IOException error ) {
	System.err.println( "Read Error : " + error );
	System.exit( 1 );
      }

      int temp = 0;

      try {
	temp = Integer.parseInt( line );
      } catch( Exception error ) {
	System.err.println( "Integer Parse Error : " + error );
	System.exit( 1 );
      }	

      S[ i ] = temp;
    }

    // read in the k we are looking for
    try {
      line = inputStream.readLine();
    } catch( IOException error ) {
      System.err.println( "Read Error : " + error );
      System.exit( 1 );
    }
    
    int k = -1;
    
    try {
      k = Integer.parseInt( line );
    } catch( Exception error ) {
      System.err.println( "Integer Parse Error : " + error );
      System.exit( 1 );
    }

    if ( k == -1 ) {
      System.err.println( "K is not valid" );
      System.exit( 1 );
    }

    // setup the K array
    int[] K = new int[ 5000 ];
    
    for( int p = 0; p < 5000; p++ ) {
      K[ p ] = 0;
    }
    for ( int p = 1; p < k; p++ ) {
      int index = ( int )( ( 5000.0 / ( double )k ) * ( double )p );
      K[ index ] = 1;
    }
    
    // reset the number of comps
    resetComp();

    // we take a constant 54.3k for k >= 500
    if ( k >= 500 ) {
      MergeInsertion.sort( S, 0, 4999 );
    } else {
      // call the findQuantiles function
      findQuantiles( S, 0, 4999, K );
    }

    // print out the quantiles
    for ( int p = 1; p < k; p++ ) {
      int index = ( int )( ( 5000.0 / ( double )k ) * ( double )p );
      System.out.println( S[ index ] );
    }

    // print out the number of comparisions we took
    System.out.println( totalComp() );
  }
}