Красивая перестановка
Рассмотрим перестановку целых чисел от 1 до n. Длину самой длинной монотонной подпоследовательности этой перестановки будем называть её уродством.
Например, уродство перестановки <1, 2, 5, 3, 4> равно 4, так как она содержит монотонную подпоследовательность (1, 2, 3, 4) длиной 4, но не имеет таковой длиной 5. Уродство перестановки <5, 6, 3, 4, 1, 2> равно 3, поскольку она имеет монотонную подпоследовательность (5, 3, 1) длиной 3.
Перестановки, которые имеют минимально возможное уродство для данного n, будем называть красивыми. Задача заключается в том, чтобы, зная n, найти первую в лексикографическом порядке красивую перестановку размера n.
Входные данные
Входной файл содержит n (1 ≤ n ≤ 10000).
Выходные данные
Выведите первую в лексикографическом порядке красивую перестановку размера n.