$7 \cdot 61$ Let $a_{1}, a_{2}, \cdots, a_{k}$ be a finite sequence of positive integers not exceeding $n$, where any term has two different adjacent terms and there do not exist any four indices $p<q<r<$ $s$, such that
$$
a_{p}=a_{r} \neq a_{q}=a_{s} .
$$

Find the maximum value of the number of terms $k$.
［Solution］It is easy to see that the following sequence
$n, n, n-1, n-1, \cdots, 2,2,1,1,2,2, \cdots, n-1, n-1, n, n$ satisfies the requirements of the problem.
This sequence has $k=4 n-2$ terms, so the maximum value of the required number of terms $k$ is no less than $4 n-2$.
Clearly, in any sequence that meets the requirements, no three consecutive terms can be the same number, and if a term has two neighbors (or one neighbor for the first or last term) that are different from that term, then when a term with the same value is added next to it, the new sequence still meets the requirements, but the number of terms increases by 1.

Therefore, when we seek the maximum number of terms, we only need to consider the number of terms in sequences where consecutive pairs of terms have the same value.

For this purpose, we only need to consider the number of terms in sequences where any consecutive pairs of terms are different. Because twice the number of terms in the latter is the number of terms in the former.

Below, we use mathematical induction to prove: If the sequence $a_{1}, a_{2}, \cdots, a_{k}$ has any consecutive pairs of terms with different values, and
$$
a_{j} \in\{1,2, \cdots, n\}, j=1,2, \cdots, k .
$$

and there does not exist such an index $p1$, then the two sets of terms
$$
\begin{array}{l}
A=\left\{a_{1}, a_{2}, \cdots, a_{v}\right\}, \\
B=\left\{a_{v+1}, \cdots, a_{k-1}\right\}
\end{array}
$$

have no terms with the same value, so if we denote the number of different values of the terms in $A$ as $s$, and the number of different values of the terms in $B$ as $t$, then
$$
s+t \leqslant m+1 .
$$

Thus, by arranging the terms in $A$ and $B$ into two sequences that both meet the requirements, and
$$
s \leqslant m, t \leqslant m .
$$

By the induction hypothesis, the number of terms in these two sequences is
$$
\begin{array}{l}
v \leqslant 2 s-1, \\
k-v-1 \leqslant 2 t-1 .
\end{array}
$$

Therefore,
$$
\begin{aligned}
k & \leqslant 2 t+v \leqslant 2 t+2 s-1 \\
& =2(t+s)-1 \leqslant 2(m+1)-1 .
\end{aligned}
$$

Thus, the induction proof is completed.
In summary, the maximum value of the required number of terms $k$ is $4 n-2$.