1853. Monotonic Subsequence

Let us consider some permutation of numbers from 1 to 10, for example (10, 1, 8, 3, 4, 7, 5, 6, 2, 9). The longest increasing subsequence is (1, 3, 4, 5, 6, 9). Its length equals 6. The longest decreasing subsequence is (10, 8, 7, 5, 2). Its length equals 5. So, the length of the most long monotonic (increasing or decreasing) subsequence equals 6.

Your program must find permutation of numbers from 1 to `N` with minimal length of the longest monotonic subsequence, where `N` is a given integer number.

The first line of the input file contains single integer `N` (`1\ ≤\ N\ ≤\ 1000`).

Write into the first line of the output file the number, which is equal to minimal length of the longest monotonic subsequence of permutation of numbers from 1 to `N`. The second line of the output file should contain such permutation `(a_1,\ a_2,\ …,\ a_N)` with mentioned property, that gives the minimal value of expression `a_1*N^{N–1}+a_2*N^{N–2}+…+a_{N–1}*N+a_N`, i.e. the first permutation in lexicographic order with mentioned property. The elements of permutation would be separated by one space.

9

3
3 2 1 6 5 4 9 8 7