35 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, with the number of terms $k=4 n-2$. Therefore, the maximum value sought is no less than $4 n-2$.
Clearly, in any sequence that meets the requirements, no three consecutive terms can be the same, and if a term has two neighbors (or one neighbor for the first or last term) that are different from it, then adding a neighbor with the same value after this term will still result in a sequence that meets the requirements, but the number of terms increases by 1. Therefore, when seeking the maximum number of terms, it is only necessary to consider sequences where each term is the same as one of its neighbors. For this, it is only necessary to consider sequences where every two consecutive terms are different. Because twice the number of terms in the latter is the number of terms in the former.
We will prove by mathematical induction: If the sequence
$$
a_{1}, a_{2}, \cdots, a_{k}
$$

has any two consecutive terms with different values and
$$
a_{i} \in\{1,2, \cdots, n\}, i=1,2, \cdots k .
$$

and there do not exist four indices $p1$, then by (*), the sequence
$$
A=\left\{a_{1}, a_{2}, \cdots, a_{V}\right\},
$$

has terms different from those in the sequence
$$
B=\left\{a_{V+1}, \cdots, a_{k-1}\right\},
$$

Therefore, if $A$ has $s$ different terms and $B$ has $t$ different terms, then
$$
s+t \leqslant m+1 .
$$

and both sequences $A$ and $B$ meet the requirements, so by the induction hypothesis
$$
\begin{array}{c}
V \leqslant 2 s-1, \\
k-V-1 \leqslant 2 t-1,
\end{array}
$$

thus
$$
k \leqslant 2(s+t)-1 \leqslant 2(m+1)-1 .
$$

That is, when $n=m+1$, the proposition also holds.
From (1) and (2), we can conclude that the proposition holds. Therefore, the maximum value of $k$ sought in the problem is $4 n-2$.
35 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$.

 untranslated part:
设 $a_{1}, a_{2}, \cdots, a_{k}$ 是以不超过 $n$ 的正整数为项的有限数列, 其中任一项的两个相邻项都不同且不存在任何四个指标 $p<q<r<s$, 使得 $a_{p}=a_{r} \neq$ $a_{q}=a_{s}$, 求项数 $k$ 的最大值。

translated part:
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$.