Such sequences do exist. It suffices to generate a large enough random sequence. If you check Dan Romik's book, [_The Surprising Mathematics of Longest Increasing Subsequences_](https://www.math.ucdavis.edu/~romik/download-book.php), Theorem 1.1 states that

$$\frac {\ell_n} {\sqrt n} \to 2,$$

where $\ell_n$ is an expected length of increasing subsequence in a random permutation of size $n$. The same for decreasing. Therefore, for large enough $n$ there must exist a sequence with both increasing and decreasing sequences of lengths at most $5 \sqrt n$, otherwise:

$$2 E[\ell_n] = E[|decr_n| + |incr_n|] \ge 5 \sqrt n,$$

which contradicts the theorem.