Level Design

The time limit is 1000 ms and the memory limit is 1024 MB.

There are $N+2$ levels numbered from $0$ to $N+1$. The levels are arranged in the order $0, 1, 2, \cdots, N, N+1$, and the player starts at level $0$ and advances in order until level $N+1$. The player cannot return to a level already visited or skip a level.

Except for room $0$ and room $N+1$, each of the $N$ rooms holds one item that adds points. If the player takes the item in room $i$, the player gains $i$ points. In each level, the player decides whether to carry the item, but the player cannot carry items in two consecutive levels.

Byungyoon wants to rearrange the items so that the maximum score the player can earn is as small as possible. The rearrangement must satisfy the following conditions.

• Rooms $1, 2, \cdots, N$ each contain exactly one item.
• Let $S_i$ be the score of the item in room $i$ after the rearrangement. $S_1, S_2, \cdots, S_N$ must be a permutation in which each integer from $1$ to $N$ appears exactly once.

Find one arrangement of items that satisfies these conditions, and find the maximum score the player can earn with that arrangement.

The first line contains an integer $N$. ($1 \le N \le 200\ 000$)

The first line prints $S_1, S_2, \cdots, S_N$ separated by spaces.

The second line prints the maximum score the player can earn with that arrangement.

If several arrangements satisfy the conditions, any of them is accepted.