// Bradley Whitmarsh
// 039 54 8497
// COM1390 - Programming Assignment 1
// February 19, 1999
//
// File: quantile.java
// -------------------
//
// This program reads 5000 integers into an array.  As each integer is
// read, it is sorted into the array.  After all of the integers have
// been read, the program calculates values such as n/k-1, n/k, etc., then
// traverses the array and uses those values to determine which elements
// form the kth quantile.  See comments throughout the program for a more
// detailed description of how this works.

import java.io.*;
import java.text.*;
import java.util.*;

public class quantile {

  // Constant value determines the number of integers to be read.
  public static final int NUM_ENTRIES = 5000;

  public static void main(String[] args) {

    // Variables used for reading from standard input.
    InputStreamReader isr = new InputStreamReader(System.in);
    BufferedReader br = new BufferedReader(isr);

    // Variable used for converting strings to integers.
    DecimalFormat df = new DecimalFormat();

    int[] intArray = new int[NUM_ENTRIES]; // array holds the integers
    int compares = 0; // total number of comparisons

    try {

      System.out.println("Reading integers, one to a line...");

      for (int i = 0; i < NUM_ENTRIES; i++) {

        // Read an integer as a string, then convert it to an integer.
        String s = br.readLine();
        Number n = df.parse(s);
        intArray[i] = n.intValue();

        // Find position in the array that new integer should go.
        int m = 0;
        while (intArray[i] > intArray[m]) {
          compares++;
          m++;
        }
        compares++;

        // Push greater values one spot to the right, to make room for
        // new integer.
        for (int j = m; j < i; j++) {
          intArray[i - (j - m)] = intArray[i - (j - m) - 1];            
        }

        // Insert new integer.
        intArray[m] = n.intValue();
      }

      // Read value for k as a string, then convert it to integer.
      String s = br.readLine();
      Number n = df.parse(s);
      int k = n.intValue();

      // Strip out the elements that form the kth quantiles.  Each of the
      // subsets will have either n/k-1 elements or n/k elements.  The
      // variable sm_size holds the value n/k-1.
      int sm_size = NUM_ENTRIES / k - 1;

      // The variable sm_num holds the number of n/k-1 sets there will be.
      // This is useful for determining the position in the array of the
      // elements that form the kth quantile.  There will be k-1 elements
      // in the kth quantile, meaning there will be n-(k-1) elements to be
      // divided into k subsets.  The number of subsets of n/k-1 elements
      // is equal to n-(k-1) mod k.  If this value is 0, then there will
      // be no subsets of n/k-1 elements, which is why we initialize
      // sm_num to 0.
      int sm_num = 0;

      // If n-(k-1) mod k is not 0, then assign it to sm_num.
      if ((NUM_ENTRIES - k + 1) % k != 0) {
        sm_num = k - ((NUM_ENTRIES - k + 1) % k);
      }
      compares++;

      int pointer = -1; // This is used to indicate our position in the
                        // array as we traverse it picking out the
                        // elements that form the kth quantile.

      // Print out the elements of the kth quantile that correspond to
      // the subsets that contain n/k-1 elements.
      for (int x = 0; x < sm_num; x++) {
        compares++;
        pointer = pointer + sm_size + 1;
        System.out.println(intArray[pointer]);
      }
      compares++;

      // Print out the elements of the kth quantile that correspond to
      // the subsets that contain n/k elements.
      for (int y = 0; y < k - sm_num - 1; y++) {
        compares++;
        pointer = pointer + sm_size + 2;
        System.out.println(intArray[pointer]);
      }
      compares++;

      System.out.println(compares + " comparisons.");

    } catch (IOException e1) {
      System.out.println("An error has occurred: " + e1);
    } catch (ParseException e2) {
      System.out.println("An error has occurred: " + e2);
    }
  }
}