Lexicographically Smallest Array with Given Inversions

Given a positive integer \(x\), find a shortest array \(A\) consisting of positive integers such that there are exactly \(x\) pairs \( (i, j) \) satisfying \(i A_j\) (i.e. exactly \(x\) inversions). If there exist multiple such arrays, output the lexicographically smallest one.

Note: The array is not required to be a permutation of \(\{1, 2, \dots, n\}\), but it turns out that the optimal answer is given by a permutation of \(\{1,2,\dots, n\}\), where \(n\) is the minimal integer such that \(\frac{n(n-1)}{2} \ge x\). In any permutation of \(\{1,2,\dots, n\}\), the maximum number of inversions is \(\frac{n(n-1)}{2}\). Therefore, let \(n\) be the smallest integer with \[ \frac{n(n-1)}{2} \ge x. \]

To construct the lexicographically smallest permutation with exactly \(x\) inversions, use the following greedy idea: maintain a sorted list of the available numbers, and for each position choose the smallest number that can produce a required number of inversions. In particular, if the available list is \(V\) (in increasing order) with \(m=|V|\), then choosing the element at index \(j\) (0-indexed) will contribute exactly \(j\) inversions (since there are \(j\) numbers smaller than it in \(V\) that will appear later). Also, the maximum inversions you can still get from the remaining \(m-1\) elements is \(\frac{(m-1)(m-2)}{2}\). Thus, you can choose the smallest index \(j\) such that \[ j + \frac{(m-1)(m-2)}{2} \ge x. \] After selecting that element, decrease \(x\) by \(j\) and remove the chosen element from \(V\). Repeat until the array is complete.

inputFormat

The input consists of a single integer \(x\) (\(0 \le x \le 10^9\)).

outputFormat

Output the elements of the array \(A\) separated by spaces in one line.

sample

0

1