Прекрасна Перестановка

Розглянемо перестановку цілих чисел від 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.

Приклади