교환 횟수가 최대인 힙 정렬

최대 힙은 배열로 표현된 힙이며, 각 원소는 자식 원소보다 크거나 같다. 인덱스 i의 자식은 존재한다면 2i와 2i+1에 있다.

힙 정렬의 삭제 단계에서는 현재 힙의 최댓값인 루트를 제거하고, 마지막 원소를 루트로 옮긴 뒤 힙 조건을 만족할 때까지 더 큰 자식과 교환한다. 이때 실제로 두 원소를 맞바꾸는 횟수를 교환 횟수라고 하자. 이 삭제 과정을 힙에 원소가 하나만 남을 때까지 반복한다.

정수 n이 주어질 때, 1부터 n까지의 수를 한 번씩 사용해 만들 수 있는 최대 힙 중에서 위 삭제 과정의 전체 교환 횟수가 최대가 되는 힙을 출력하시오.

첫째 줄에 정수 n이 주어진다. (1 <= n <= 100,000)

첫째 줄에 힙을 나타내는 n개의 정수를 공백으로 구분해 출력한다.