A permutation of length $n$ is a sequence containing every integer $x$ such that $1 \le x \le n$ exactly once.

For a permutation $A = \{a_i\}$, we define its number of cycle components $R(A)$ as the number of connected components in the undirected graph $G = \{V, E\}$, where $V = \{i \mid 1 \le i \le n\}$ and $E = \{(i, a_i) \mid 1 \le i \le n\}$.

The weight $V(A)$ of a permutation $A = \{a_i\}$ is defined as the sum of the number of cycle components of the $n$ permutations that are cyclically equivalent to $A$. Specifically, two permutations $P$ and $Q$ are cyclically equivalent if and only if $P$ can be transformed into $Q$ through a series of right-shift operations (i.e., moving the last element of $P$ to the front of $P$).

For example, the weight of $\{1, 2, 3, 4\}$ is the sum of the number of cycle components of $\{1, 2, 3, 4\}, \{4, 1, 2, 3\}, \{3, 4, 1, 2\}, \{2, 3, 4, 1\}$, which is $4 + 1 + 2 + 1 = 8$.

Given an integer $n$, you need to find a permutation $A$ of length $n$ that maximizes its weight $V(A)$. You must output the value of $V(A)$ and the permutation $A$.

Input

A single integer $n$ ($1 \le n \le 10^3$).

Output

Output the maximum weight on the first line. On the second line, output the $n$ integers of the permutation separated by spaces. If there are multiple solutions, you may output any one of them.

Examples

Input 1

3

Output 1

6
1 3 2