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

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