3. Given an integer $n \geqslant 3$, a finite sequence is called an “$n$-sequence” if it satisfies conditions (1) and (2):
(1) The sequence has at least three terms, and each term's value belongs to the set $\{1,2, \cdots, n\}$;
(2) If the sequence has $m$ terms, denoted as $a_{1}, a_{2}, \cdots, a_{m}$, then for $k=1,2, \cdots, m-2$, it holds that $\left(a_{k+1}-a_{k}\right)\left(a_{k+2}-a_{k}\right)<0$.
Find the number of $n$-sequences. (Proposed by He Yijie)
3. Consider any $m$-term $n$-sequence $S_{0}$:
$$
a_{1}, a_{2}, \cdots, a_{m} \text {. }
$$

From condition (1), we know $m \geqslant 3$.
According to condition (2), for $k=1,2, \cdots, m-2$, we have
$$
\min \left\{a_{k+1}, a_{k+2}\right\}a_{m-2}>\cdots>a_{1}>a_{2}>a_{4}>\cdots>a_{m-1} \text {; (2) }
$$

When $m$ is even,
$$
a_{m}>a_{m-2}>\cdots>a_{2}>a_{1}>a_{3}>\cdots>a_{m-1} \text {. }
$$

【Case 2】 $a_{m}$ is the smallest term in $S_{0}$.
Similarly to Case 1, when $m$ is odd,
$$
a_{m}<a_{m-2}<\cdots<a_{1}<a_{2}<a_{4}<\cdots<a_{m-1} \text {; (4) }
$$

When $m$ is even,
$$
a_{m}<a_{m-2}<\cdots<a_{2}<a_{1}<a_{3}<\cdots<a_{m-1} \text {. (5) }
$$

Conversely, when $S_{0}$ satisfies one of the equations (2) to (5), by equation (1), $S_{0}$ must satisfy condition (2).

Therefore, each $m(m \geqslant 3)$-element subset of the set $\{1,2, \cdots, n\}$ corresponds to two $n$-sequences, one of which satisfies equation (2) or (3), and the other satisfies equation (4) or (5).

Note that, the number of $m(m \geqslant 3)$-element subsets of $\{1,2, \cdots, n\}$ is $2^{n}-\mathrm{C}_{n}^{0}-\mathrm{C}_{n}^{1}-\mathrm{C}_{n}^{2}$.
Thus, the number of $n$-sequences is
$$
2\left(2^{n}-\mathrm{C}_{n}^{0}-\mathrm{C}_{n}^{1}-\mathrm{C}_{n}^{2}\right)=2^{n+1}-n^{2}-n-2
$$