28. Let $n$ be a positive integer. A sequence of $n$ positive integers (which may be equal) $a_{1}, a_{2}, \cdots, a_{n}$ is called a "full sequence" if it satisfies the following condition: for any positive integer $k (k \geqslant 2)$, if $k$ is one of the terms in the sequence, then $k-1$ is also a term in the sequence, and the first occurrence of $k-1$ in the sequence is before the last occurrence of $k$. How many "full sequences" are there for each $n$?
（43rd IMO Shortlist Problem）
28. Suppose there are $S_{n}$ full sequences. By enumeration, we can get $S_{1}=1, S_{2}=2, S_{3}=6$. Thus, we conjecture that $S_{n}=n!$. To prove this conclusion, we only need to prove that the set $X_{n}$ of all full sequences of $\{1,2, \cdots, n\}$ and the set $Y_{n}$ of all permutations of $\{1,2, \cdots, n\}$ are in one-to-one correspondence. Let $a_{1}, a_{2}, \cdots, a_{n}$ be a full sequence, and $r=\max \left\{a_{1}, a_{2}, \cdots, a_{n}\right\}$. Then, all positive integers from 1 to $r$ appear in this sequence. Let $S_{k}=\left\{i \mid a_{i}=k\right\}(1 \leqslant k \leqslant r)$ be the set of indices where $k$ appears in this sequence. Thus, $S_{k}$ is non-empty, and $\{1,2, \cdots, n\}=S_{1} \cup S_{2} \cup \cdots S_{r}, S_{i} \cap S_{j}=\varnothing(1 \leqslant i<j \leqslant r)$. 

Define a mapping $f: X_{n} \rightarrow Y_{n}$ as follows: For any full sequence $a_{1}, a_{2}, \cdots, a_{n}$, let $r=\max \left\{a_{1}, a_{2}, \cdots, a_{n}\right\}$. Let $n_{0}=0$, and for $1 \leqslant k \leqslant r$, let $n_{k}=\max S_{k}$. Then, we have $b_{1}>b_{2}>\cdots>b_{n_{1}}$, but $b_{n_{1}}<b_{n_{1}+1}<b_{n_{1}+2}>\cdots>b_{n_{2}}$ but $b_{n_{2}}<b_{n_{2}+1}<b_{n_{2}+2}>\cdots>b_{n_{3}}$, and so on, until $b_{n_{r-1}}<b_{n_{r-1}+1}<b_{n_{r-1}+2}>\cdots>b_{n_{r}}\left(n_{r}=n\right)$. Let $S_{k}=\left\{b_{n_{k-1}+1}, b_{n_{k-1}+2}, \cdots, b_{n_{k}}\right\}\left(k=1,2, \cdots, r, n_{0}=1\right)$. When $j \in S_{k}$, let $a_{j}=k(1 \leqslant k \leqslant r)$. Then the sequence $a_{1}, a_{2}, \cdots, a_{n}$ is a full sequence, and under the mapping $f$, $a_{1}, a_{2}, \cdots, a_{n}$ corresponds to $b_{1}, b_{2}, \cdots, b_{n}$. Therefore, $f$ is a surjection, and thus $f$ is a bijection. Hence, $S_{n}=\left|X_{n}\right|=\left|Y_{n}\right|=n!$.