Arrange the numbers $1,2,...,9$ in such an order that no four of them appear (adjacently or otherwise) in ascending or descending order. Show that there is no arrangement of the numbers $1,2,...,10$ with this property.
Now suppose $n>1$, and find the maximum $k$ such that the numbers $1,2,...,k$ can be arranged with no $n$ of them in ascending or descending order.
For the first question consider this sequence $5\ 3\ 7\ 1\ 9\ 4\ 2\ 8\ 6$. None $4$ of them are increasing or decreasing.