P6324 [COCI 2006/2007 #4] JOGURT

You are given a complete binary tree with a total of $n$ levels. We label the root as being on level $0$. The two children of the root are on level $1$, and so on. Now, we need to fill the $2^n - 1$ numbers from $1$ to $2^n - 1$ into the nodes, with no repetition and no omission, such that for any $d$, if we take a node on level $d$ as the root of a subtree, then the absolute value of the difference between the sum of numbers in its left subtree and the sum of numbers in its right subtree is equal to $2^d$. Please output one feasible assignment. You only need to output the [preorder traversal](https://baike.baidu.com/item/%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86/6442839?fr=aladdin) of this assignment.

One line with one integer $n$, representing the number of levels of the tree.

Output one line with $2^n - 1$ integers from $1$ to $2^n - 1$, separated by spaces, representing one possible preorder traversal. **If there are multiple answers, output any one of them. This problem uses SPJ**.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \le n \le 15$. #### Notes **This problem is translated from [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #4](https://hsin.hr/coci/archive/2006_2007/contest4_tasks.pdf) *T5 JOGURT***. Thanks to @[一扶苏一](https://www.luogu.com.cn/user/65363) for providing the SPJ. Translated by ChatGPT 5