These are the permutations that avoid the generalized permutation pattern $ 1-32$. There's a lot of literature on generalized permutation patterns -- a nice survey paper is at arXiv:0801.2412v2. This is a nice easy problem, and I'll leave the proof for others to find.

Cool problem. Call permutations satisfying the condition of the problem tasty. We'll establish a bijection between partitions of the set $[n]$ and the tasty permutation of $[n]$. For the forward direction, consider some partition $[n] = S_1 \cup S_2 \cup \cdots \cup S_k$, where the sets $S_i$'s are in increasing order based on their minimal element. Then, map this partition to the permutation which consists of the elements of $S_1$ in descending order, then the elements of $S_2$ in descending order, then the elements of $S_3$ in descending order, etc. For example, if our partition is $\{1, 3, 4\} \cup \{2, 5\} \cup \{6, 9\} \cup \{7, 8\}$, then it is mapped to the permutation $431529687.$ It's not hard to verify that the permutations obtained in this manner are all tasty, and that no two partitions map to the same tasty permutation. This implies that the number of tasty permutations is at least the number of partitions of $[n]$. For the reverse direction, consider a permutation $\alpha$ of $n$ and draw bars in the spaces where the permutation increases. For instance, if our permutation is $431529687$, then we add in spaces like so: $431 | 52 | 96 | 87.$ Now treat the bars as dividers, and consider the partition of $[n]$ which simply comprises of the sets of numbers delineated by the bars. In the case of our example, $431529687$ is mapped to $\{4, 3, 1\} \cup \{5, 2\} \cup \{9, 6\} \cup \{8, 7\}.$ It's not hard to verify that this operation is the exact reverse of the first operation, and this shows that the number of tasty permutation is exactly equal to the number of partitions of $[n]$. $\square$

Consider an arbitrary partition of $[n]$, with each part sorted in increasing order, and the parts sorted from largest to smallest minimum element. Then, concatenating the parts in their current order gives a unique, valid $\alpha$. To reverse this process, consider the set of all elements in $\alpha$ such that they are smaller than any number before them. Note that if at any point $\alpha$ decreases over consecutive terms, it must be at one of these points, or else the condition is violated. So, taking these points to be the start of our parts in the partition gives all parts to be in increasing order, and hence our initial partition. As there exists a bijection, these two quantities are equal, as desired.