Heap Sort With the Maximum Number of Swaps

A max-heap is represented as an array, and every element is greater than or equal to its children. For an index i, its children are at 2i and 2i+1 if those indices exist.

During the deletion phase of heap sort, the root, which is the maximum element of the current heap, is removed. The last element is moved to the root, then repeatedly swapped with the larger child until the heap property is restored. Count one swap each time two elements are actually exchanged. Repeat this deletion process until only one element remains in the heap.

Given an integer n, output a max-heap made by using each integer from 1 through n exactly once, such that the total number of swaps in the deletion process above is as large as possible.

The first line contains an integer n. (1 <= n <= 100,000)

Print n space-separated integers on the first line, representing the heap.