Consider a permutation of integer numbers from 1 to n. Let us call length of the longest monotonic subsequence of the permutation its ugliness.
For example, the ugliness of the permutation <1, 2, 5, 3, 4> is 4 because it has a monotonic subsequence (1, 2, 3, 4) of length 4, but has none of length 5. The ugliness of the permutation <5, 6, 3, 4, 1, 2> is 3 because it has a monotonic subsequence (5, 3, 1) of length 3.
Let us call beautiful those permutations that have a smallest possible ugliness for given n. Given n, you must find the first in lexicographic order beautiful permutation of size n.
Input file contains n (1 ≤ n ≤ 10000).
Output the first in lexicographic order beautiful permutation of size n.