// Raul Grau
// Kasia Leskow

import java.io.*;
import java.lang.*;
import java.util.*;
import java.math.*;

public class com1390a{

 public static void main(String args[]) {
  int comp = 0;
  int n = 5000;
  int[] A = new int[n];

  // here we assign 5000 random numbers 
  // between 0 and 100 
  for (int i = 0; i < n; i++) 
     A[i] = (int)(Math.random()*100);


  // here we do the sort
  Heap h = new Heap(A);
  h.Heapsort(comp);
  comp = h.GetComp();
  System.out.println("Comp "+comp);

  //sorted
  //for(int i = 0;i<10;i++)
    // System.out.println("Numerki"+A[i]+" ");


  // this is for k =2?
  int k = 5; 
  double f = (double)k;
   
  double x;
 
  // print line
  System.out.println("");
  // we get the comp here
  for(int i =0; i <k-1; i++){ 
   x =((i+1)*(Math.ceil(n/f))) -2;
   int xx = (int)x;
    comp++;
    System.out.println("Number "+i+" "+A[xx]);
   }
 

  System.out.println("Number of comparisons is: "+comp);
 }
}
class Heap extends com1390{
 int[] A = null;
 int comp1=0;

 public Heap(int[] A){
  this.A = A;
  
 }
  
 public int[] Heapsort(int comp){
  comp1 = comp;
  A = BuildHeap(A); // good     

  int l = A.length-1; 
  for(int i = l ; i>=0; i--){
  
   int t = A[i];
   A[i] = A[0];
   A[0] = t;
     
   l--;
   Heapify(A,0,l);
 
  }

    return A;
 }

 public int[] BuildHeap(int[] A){
  double f = Math.floor((A.length)/2); 
  int l = (int)f;
 

  for(int i = l; i>=0; i--){
   Heapify(A,i,A.length);
      
  }
  return A;
 }

 public int GetComp(){
  return comp1;
 }

 public int[] Heapify(int[] A, int i,int len){
  
  int l = 2*i+1;
  int r = (2*i)+2;

  int largest;

  
  if(l < len && A[l]>A[i]){
   comp1++;
   largest = l;
  }
  else
   largest = i;
  
  
  if(r < len && A[r]>A[largest]){
   comp1++;
   largest = r;
  }
  
  if (largest !=i){
  
   int t = A[i];
   A[i] = A[largest];
   A[largest] = t;
  
   Heapify(A,largest,len);
  }
   return A;

 }

}