2 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_{1} \neq a_{q}=a_{s}$. Find the maximum value of $k$.


2. The sequence $n, n, n-1, n-1, \cdots, 2,2,1,1,2,2, \cdots, n-1, n-1, n, n$ meets the requirement, because if $a_{i}=a_{j}$, then $i$ and $j$ must be adjacent or symmetric about the middle two terms 1,1. Therefore, the maximum value of $k$ is no less than $4 n-2$. Furthermore, in any sequence that meets the conditions, no three consecutive terms can be the same. Moreover, if a term in the sequence has all its neighbors (note that the first and last terms have only one neighbor) different from it, then adding a term identical to it next to it will still satisfy the condition. Thus, we only need to consider sequences where every two consecutive terms are the same. Further, we only need to study the number of terms in sequences where every two consecutive terms are different (by removing one term from each pair of identical consecutive terms). Below, we use induction to prove: if in the sequence $a_{1}, a_{2}, \cdots, a_{k}$ any two consecutive terms are different, each term is a natural number no greater than $n$, and there do not exist any four indices $p1$, then let $A=\left\{a_{1}, a_{2}, \cdots, a_{v}\right\}, B=\left\{a_{v+1}\right.$, $\left.a_{v+2}, \cdots, a_{k-1}\right\}$, then $A$ and $B$ do not have any consecutive identical terms, and the terms in $B$ are in $\{1$, $2, \cdots, n\} \backslash\{t\}$, and the terms in $A$ are in $\{1,2, \cdots, n\} \backslash\{B\}$, thus both can use the induction hypothesis. Let the number of distinct terms in $A$ be $p$, and the number of distinct terms in $B$ be $q$, then $p+q \leqslant n$. This way, applying the induction hypothesis to $A$ and $B$ respectively, we have $v \leqslant 2 p-1, k-v-1 \leqslant 2 q-1$. Therefore, $k \leqslant 2 q+$ $v \leqslant 2 q+2 p-1=2(p+q)-1 \leqslant 2 n-1$. Hence, the maximum value of $k$ is $4 n-2$.