원문에서의 입력 조건은 n (1 ≤ n ≤ 50 000) 인데 번역에서는 n의 최댓값이 100,000입니다. 그리고 assert 문을 통해 n이 5만 초과인 입력이 있음을 확인했습니다. 원문을 수정하거나 원문과 다름 태그를 붙여주세요.

또한 번역문에서도 원문에 비해 설명이 부족합니다. 번역문의 설명을 바꿔주세요.

"In this problem you have to find a heapified array containing different numbers from 1 to n, such that when converting it to a sorted array, the total number of exchanges in all sifting operations is maximal possible."

1부터 n까지의 수를 한 번씩 사용하여 만들 수 있는 힙 구성된 배열중 정렬된 배열로 바꾸기 위해 필요한 sifting 연산에서 교환 횟수를 최댓값으로 만드는 배열을 찾으라고 되어 있습니다.

한국어 문제에서는 힙 조건과 sifting 연산이 어떻게 수행되는지 나와 있지 않아 사전지식에 의존해야합니다. 
이 때 문제는 힙에는 binary-heap만 있는 것이 아니라 다양한 종류의 힙이 있고 같은 힙이라도 구현이 다를 수 있기 때문에 원문에 주어져 있는 '힙 조건'과 'sifting 연산'에 대한 설명이 있어야 합니다. 

원문에서 힙 정렬에 대한 설명을 자세하게 하고 있어 오히려 가독성이 떨어질 수 있으나, 힙 정렬을 모르는 사람도 이 문제를 풀 수 있게 해야하고, 현재 번역은 모호성이 존재하므로 수정되어야합니다.

제가 번역한 원문입니다. 

잘 알려진 힙 정렬 알고리즘은 O(n log n)의 시간과 O(1)의 추가 메모리를 사용하는 결정론적 정렬 알고리즘이다. 서로 다른 정수 배열을 정렬하는 과정을 설명하면 아래와 같다.

알고리즘은 두 단계로 이루어져있다. 첫번째 단계는 힙 구성이라고 불리는데, 정렬한 정수 배열이 힙으로 변환되는 단계이다. 모든 1 ≤ i ≤ n에 대해 다음 힙 조건이 충족되면 정수의 배열 a[1 ... n]을 힙이라 한다.

• 2i ≤ n이면 a[i] > a[2i]
• 2i + 1 ≤ n이면 a[i] > a[2i + 1]

원소 a[i]의 자식을 a[2i] 와 a[2i + 1]로 간주하면 배열을 이진 트리로 해석할 수 있다. 이 경우 a[i]의 부모는 a[i 를 2로 나눈 몫]이다.

두번째 단계는 힙을 정렬된 배열로 바꾸는 단계이다. 힙 조건으로 인하여 힙 구성된 배열에서 최대 원소는 a[1]이다. a[1]과 a[n]을 교환하면 최대 원소는 정렬된 배열에서의 올바른 위치에 있게 된다. 이 과정을 최댓값 추출이라 한다.

이제 배열의 일부 a[1 ... n - 1]를 고려하자. i = 1일때 힙 조건을 만족하지 않을 수 있기 때문에 이는 힙이 아닐 수 있다. 만약 힙 조건이 만족하지 않는 경우(즉, a[2] 또는 a[3]이 a[1]보다 큼) a[1]의 자식중 가장 큰 값을 가지고 있는 자식과 교환한다. 그러면, 이제 이전의 조건 a[1]을 포함하는 위치에 대해 다시 힙 조건이 만족하지 않을 수 있다. 같은 방법을 적용해서 가장 큰 값을 가진 자식과 교환한다. 계속 반복 진행하여 a[1 ... n - 1]을 힙으로 변환시킬 수 있다. 이 과정을 선별이라 한다. 선별을 통해 배열의 일부 a[1 ... n - 1]을 힙으로 변환 시킨 다음 최댓값 추출을 통해 배열의 두번째로 큰 요소를 a[n - 1]에 넣는다. 이러한 과정을 반복하면 전체 힙을 정렬된 배열로 변환할 수 있다.

예를 들어 a = (5, 4, 2, 1, 3)라는 힙이 어떻게 정렬된 배열로 바뀌는지 살펴 보자. 첫 번째 최댓값 추출을 하게 되면 배열은 (3, 4, 2, 1,5)로 바뀐다. 이 때, a[1] = 3이 자식 a[2] = 4로 인해 힙 조건이 만족하지 않으므로 a[1]과 a[2]를 교환한다. 이제 배열은 (4, 3, 2, 1, 5)이 된다. 모든 원소에 대해 힙 조건을 만족하므로 선별 과정이 끝나게 된다. 이제 다시 최댓값 추출을 하자. 배열은 (1, 3, 2, 4, 5)로 바뀌게 된다. 다시 한 번 힙 조건은 a[1]에 대해 만족하지 않게 된다. 선별 과정을 거치게 되면 배열은 (3, 1, 2, 4, 5)가 된다. 다시 최댓값 추출을 하면 (2, 1, 3, 4, 5)가 된다. 이번에는 힙 조건이 만족하므로 선별 작업을 거치지 않고 바로 최댓값 추출을 반복한다. 그러면 배열 (1, 2, 3, 4, 5)가 된다. 이 때 배열의 맨 앞은 힙이며 마지막으로 최댓값 추출을 하여 최종적으로 (1, 2, 3, 4, 5)라는 정렬된 배열을 얻게 된다.

문제는 1부터 n까지의 수를 한 번씩 사용하여 힙 구성된 배열 중, 정렬된 배열로 바꾸기 위해 필요한 선별 연산에서의 원소 교환 횟수를 최댓값으로 만드는 배열을 찾는 것이다. 위에 있는 예에서 선별 연산에서의 원소 교환 횟수는 1 + 1 + 0 + 0 + 0 = 2다. 그러나 이는 최댓값이 아니다. 배열 (5, 4, 3, 2, 1)은 선별 연산에서 교환을 4번하고 이는 n = 5일때 최댓값이다. 

입력
첫째 줄에 n이 주어진다. (1 ≤ n ≤ 100,000)

출력

1부터 n까지의 수를 한 번씩 사용하여 힙 구성된 배열 중, 정렬된 배열로 바꾸기 위해 필요한 선별 연산에서의 원소 교환 횟수를 최댓값으로 만드는 배열을 출력한다. 각 수들은 띄어쓰기로 구분하여 출력한다.