Beautiful Permutation

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$.