public static void main(String[] args)

 {

     Scanner input = new Scanner(System.in);

     int n = input.nextInt();

     int[] a = new int[n];

     a[0] = 0;  //不使用第一个位置

     for(int i = 1; i < a.length; i++)

         a[i] = (int)(Math.random() * 100);

     //System.out.println(Arrays.toString(a));

     long start = System.currentTimeMillis();

     heapsort(a, a.length - 1);

     long end = System.currentTimeMillis();

     //System.out.println(Arrays.toString(a));

     System.out.println(end - start);

     //10000000个测试数据用时1050ms 100000000个测试数据用时11500ms

 }

 public void static heapsort(int[] a, int n)

 {

     for(int i = n / 2; i >= 1; i--)

     sink(a, i, n);

     while(n > 1)

     {

     int temp = a[n];

     a[n--] = a[1];

     a[1] = temp;

     sink(a, 1, n);

     }

 }

 public static void sink(int[] a, int k, int n)  //最小堆化

 {

     while(k <= n / 2)

     {

     int min_index = k * 2;

     if(min_index + 1 <= n && a[min_index + 1] < a[min_index])

         min_index++;

     if(a[k] > a[min_index])

     {

         int temp = a[k];

         a[k] = a[min_index];

         a[min_index] = temp;

         k = min_index;

     }

     else

         break;

     }

 }