A finite sequence of non-negative integers $a_{1}, a_{2}, \cdots, a_{n}\left(a_{1}=0\right)$ satisfies the following conditions:
(a) When $k \geqslant 2$, $a_{k} \leqslant u_{k}+1$. Here, $u_{2}=0$; when $k \geqslant 3$, $u_{k}$ is the number of elements in the set $\left\{i \mid a_{i}<a_{i+1}, 1 \leqslant i \leqslant\right.$ $k-2\}$.
(b) There do not exist $i, j, k(1 \leqslant i<j<k \leqslant n)$ such that $a_{j}<a_{i}<a_{k}$.
Find the number of such sequences.
Let the set of sequences satisfying the conditions be $A_{n}$, and the set of sequences where at least one of $a_{2}, \cdots, a_{n}$ is 0 be $B_{n}$. Let $f(n)=\left|A_{n}\right|, g(n)=\left|B_{n}\right|$, then $f(1)=1, g(1)=0, f(2)=2, g(2)=1$.

On one hand, in $A_{n} \backslash B_{n}$, the sequences $a_{2}, \cdots, a_{n}$ are all greater than 0 (where $a_{2}=1$), so $a_{2}-1, \cdots, a_{n}-1$ are sequences in $A_{n-1}$. Conversely, by adding 1 to each term of the sequences in $A_{n-1}$ and shifting them one position to the right, and then adding $a_{1}=0$, we get sequences in $A_{n} \backslash B_{n}$. Therefore, for $n \geqslant 2, A_{n} \backslash B_{n}$ corresponds one-to-one with $A_{n-1}$, i.e.,
$$
f(n)-g(n)=f(n-1) .
$$

On the other hand, for $n \geqslant 3$, the set $B_{n}$ can be divided into the following three subsets.
(1) $a_{n}=0$ or $1, a_{2}, \cdots, a_{n-1}$ contain at least one 0. These sequences (excluding $a_{n}$) correspond to $B_{n-1}$ in a 2-to-1 manner, so their number is $2 g(n-1)$.
(2) $a_{n}=0, a_{2}, \cdots, a_{n-1}$ are all greater than 0. These sequences (excluding $a_{n}$) correspond one-to-one with $A_{n-1} \backslash B_{n-1}$, so their number is $f(n-1)-g(n-1)=f(n-2)$.
(3) $a_{n} \geqslant 2, a_{2}, \cdots, a_{n-1}$ contain at least one 0. Let the last 0 be $a_{k}(2 \leqslant k \leqslant n-1)$. If $a_{2}, \cdots, a_{k-1}$ contain a term greater than 0, the first such term is $a_{i}=1$, then $(i, k, n)$ violates condition (b), so $a_{1}, \cdots, a_{k}$ are all 0. Removing $a_{1}, \cdots, a_{k-1}$, these sequences correspond one-to-one with sequences in $A_{n-k+1} \backslash B_{n-k+1}$ with the last term not less than 2. Sequences with the last term equal to 1 correspond one-to-one with sequences in $A_{n-k} \backslash B_{n-k}$. Therefore, for a fixed $k$, the number of such sequences is $f(n-k)-f(n-k-1)$. Summing over $k$ gives the total number of such sequences as $f(n-2)-1$.
Thus, we obtain the recurrence relation
$$
g(n)=2 g(n-1)+2 f(n-2)-1 .
$$

Eliminating $g(n)$ from the two equations, we get $f(n)=3 f(n-1)-1$. Combining with the initial values, we can recursively obtain $f(n)=\frac{3^{n-1}+1}{2}$.