Problem Description

Given an integer $n$, the initial sequence looks like this:

$$\underbrace{\tt 111\cdots11}_{n \text{ ones}}\underbrace{\tt 000\cdots00}_{n \text{ zeros}}\verb!__!$$

Now you need to use the minimum number of swaps to make the final sequence become:

$$\underbrace{\tt 101010\cdots 1010}_{2\times n \text{ digits with alternating } 0 \text{ and } 1}\verb!__!$$

A swap means moving two adjacent non-blank digits together onto the two blanks.

For example, the following is a valid solution when $n=4$:

• Initial state: $\verb!11110000__!$.
• Step $1$: $\verb!__11000011!$.
• Step $2$: $\verb!101__00011!$.
• Step $3$: $\verb!1010100__1!$.
• Step $4$: $\verb!10101__001!$.
• Step $5$: $\verb!10101010__!$.

It can be proven that the minimum number of operations is $5$.

Input Format

The input contains one line with an integer $n$.

Output Format

Output the minimum number of moves in the first line.

In the next line, output a move plan. You only need to output the index of the left one of the two moved non-blank cells. See the sample for details.

4

5
1 4 8 6 9

Hint

For $100\%$ of the testdata, $2<n\le 2\times 10^5$.

Translated by ChatGPT 5