print1853. Monotonic Subsequence

printMonotonic Subsequence

Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.
Input
The first line of the input file contains single integer `N` (`1\ ≤\ N\ ≤\ 1000`).
Output
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.

Sample Input

9

Sample Output

3
3 2 1 6 5 4 9 8 7
loading