3. Let $n$ be a positive integer. If a sequence of $n$ positive integers (which can be the same) is called "full", then this sequence should satisfy the condition: for each positive integer $k (k \geqslant 2)$, if $k$ is in this sequence, then $k-1$ is also in this sequence, and the first occurrence of $k-1$ is before the last occurrence of $k$. How many "full" sequences are there for each $n$?
(Colombia provided)
Solution: There are $n$! "full" sequences.
To prove this conclusion, we construct a "full" sequence that is in bijection with the permutations of the set $\{1,2, \cdots, n\}$.

Let $a_{1}, a_{2}, \cdots, a_{n}$ be a "full" sequence, $r=$ $\max \left\{a_{1}, a_{2}, \cdots, a_{n}\right\}$. Then, all integers from 1 to $r$ appear in this sequence. Let $S_{i}=\left\{k \mid a_{k}=i\right\}, 1 \leqslant i \leqslant r$, then all $S_{\mathrm{t}}$ are non-empty, and they form a partition of the set $\{1,2, \cdots, n\}$. For 2 $\leqslant k \leqslant r$, the "full" sequence also satisfies $\min S_{k-1}b_{2}>\cdots>b_{k_{1}}$, and $b_{k_{1}}b_{k_{1}+2}>\cdots>b_{k_{2}}$, and $b_{k_{2}}b_{k_{t-1}+2}>\cdots>b_{n}$.
When $j \in S_{i}, 1 \leqslant i \leqslant t$, let $a_{j}=i$, then the sequence $a_{1}, a_{2}$, $\cdots, a_{n}$ is a "full" sequence.

In summary, the set of "full" sequences is in bijection with the set of permutations of $\{1,2, \cdots, n\}$.