Good Sequences

For all $n \in \mathbb{N},$ a sequence $(x_1, x_2, \cdots , x_n)$ of positive integers (not necessarily distinct) is called good if

• for all $k \geq 1,$ if $k+1$ appears in the sequence, so does $k$ , and
• the first occurrence of $k$ happens before the last occurrence of $k+1$ (i.e. if $j$ is the smallest integer such that $x_j=k$ and $h$ is the largest integer such that $x_h= k+1,$ then $j<h$ ).

Find the number of good sequences of length $5$ .

Details and assumptions

• This problem is not original.
• The five integers need not be distinct.
• For example, $(1, 2, 3, 4,5)$ and $(1,2, 4, 3, 4)$ are two good sequences of length $5$ .