9. (2000 Shanghai Competition Problem) Let $a_{1} a_{2} a_{3} a_{4} a_{5}$ be a permutation of $1,2,3,4,5$, satisfying that for any $1 \leqslant i \leqslant 4$, $a_{1} a_{2} a_{3} \cdots a_{i}$ is not any permutation of $1,2, \cdots, i$. Find the number of such permutations.
9. Let $A_{i}=\left\{a_{1} a_{2} \cdots a_{i} \mid a_{1} a_{2} \cdots a_{i}\right.$ be exactly a permutation of $1,2, \cdots, i\}$ $(i=1,2, \cdots, 5)$, then the number of permutations that meet the condition is $\left|\overline{A_{1}} \cap \overline{A_{2}} \cap \overline{A_{3}} \cap \overline{A_{4}} \cap \overline{A_{5}}\right|=|S|-\sum_{i=1}^{5}\left|A_{i}\right|+\sum_{1 \leqslant i<j \leqslant 5} \mid A_{i} \cap$ $A_{j}\left|-\sum_{1 \leqslant i<j<k \leqslant 5}\right| A_{i} \cap A_{j} \cap A_{k}\left|+\sum_{1 \leqslant i<j<k<t \leqslant 5}\right| A_{i} \cap A_{j} \cap A_{k} \cap A_{t}|-| A_{1} \cap A_{2} \cap A_{3} \cap A_{4} \cap A_{5} \mid=5!-$ $(4!+2!\cdot 3!+3!\cdot 2!+4!)+(3!+2!\cdot 2!+3!+2!\cdot 2!+2!\cdot 2!+3!)-(2!+2!+$ $2!+2!)+1=120-72+30-8+1=71$. (The reasons for the above calculations are left to the reader. For example, the permutations in $A_{2} \cap A_{3}$ are only in the form $\times \times 3 \times \times$, so $\left.\left|A_{2} \cap A_{3}\right|=2!\cdot 2!.\right)$