Codebreaking#6283
Alan is fascinated by cracking codes and combination locks. Recently, he encountered an exceptionally intricate lock but couldn't find the key. Determined to unlock it, he decided to try every possible combination.
The lock features buttons, each labeled with integers from to . The lock will only open when a specific secret permutation of consecutive button presses is entered. The buttons must be pressed one at a time in sequence; pressing multiple buttons simultaneously is not an option.
To put it more precisely: suppose Alan presses the buttons times. Let a_i (1 \leq i \leq k) represent the button number Alan presses on the -th attempt, and b_1, b_2, ..., b_n denote the secret permutation. The lock will open if there exists a number (1 \leq x \leq k - n + 1) such that b_1 = a_x, b_2 = a_{x+1}, ..., b_n = a_{x+n-1}.
Alan aims to create a universal sequence of button presses that will unlock the lock for any secret permutation. He also wants to ensure that this sequence is not excessively long, specifically, it should not exceed a length of , where n! = 1 \cdot 2 \cdot ... \cdot n. For instance, if n = 3, the sequence length should not be more than .
Your task is to help Alan find such a sequence.
The input consists of a single line containing an integer (1 \leq n \leq 9) — the number of buttons on the combination lock.
In the first line of the output, print the number (0 \leq k \leq 2n!) — the length of the universal sequence. In the second line, print integers a_i, separated by spaces (1 \leq a_i \leq n) — indicating the order in which the buttons should be pressed. Note that it is sufficient to provide any sequence with a length not exceeding ; minimizing the length is not necessary. It is guaranteed that such a sequence exists for any .
Example 1