Answer: 461

Solution:

The condition fails exactly when the first $k$ terms are a permutation of $\{1, \ldots, k\}$ for some $k \le 5.$ For a permutation of $1, \ldots, n,$ let $k$ be the smallest length for which the prefix is $\{1, \ldots, k\}$ (the full length $n$ always works), and let $c_n$ be the number of permutations whose smallest such $k$ is $n.$ We want $c_6.$

Every permutation of $1, \ldots, n$ decomposes uniquely as a minimal prefix of length $k$ ($c_k$ choices) followed by any arrangement of the remaining $n - k$ values, so $$\sum_{k=1}^{n} c_k \,(n-k)! = n!.$$ Starting from $c_1 = 1,$ this gives $c_2 = 1,$ $c_3 = 3,$ $c_4 = 13,$ $c_5 = 71,$ and $$\begin{aligned} c_6 &= 720 \\ &\quad {}- \tiny(120 \cdot 1 + 24 \cdot 1 + 6 \cdot 3 + 2 \cdot 13 + 1 \cdot 71) \\ &= 720 - 259 = 461. \end{aligned}$$