Let's call a sequence $a\_1, \ldots, a\_n$ *suitable* if for any positive integer $d$ there is at most one index $i$ such that $a\_i = a\_{i + d}$ and all elements $a\_{i + 1}, \ldots, a\_{i + d - 1}$ are not equal to $a\_i$.


For each $k$, I'm interested in longest suitable sequences with all elements in $\{0, \ldots, k - 1\}$. There is a suitable sequence of length $3k - 1$: start with numbers $0, \ldots, k - 1$ in order, followed by first $2k - 1$ elements of [A025480](http://oeis.org/A025480). E.g., for $k = 3$ this sequence would look as follows: $0, 1, 2, 0, 0, 1, 0, 2$. It isn't difficult to prove that this pattern works for any $k$.


With brute-force I've discovered a few curious observations:


* $3k - 1$ appears to be the maximum length of a suitable sequence with elements in $\{0, \ldots, k - 1\}$;
* The number of longest suitable sequences appears to be $k! \times $[A002047](http://oeis.org/A002047)$[k]$.


How can this be explained?



Distinct distances between adjacent equal elements
This can be explained as follows.


Assume that $(a\_1,\ldots,a\_{n})$ is a suitable sequence.
For every $j\in \{0,\ldots,k-1\}$ denote $A(j)=\{i:a(i)=j\}$ and denote by $m(i)$ and $M(i)$ the minimal and maximal, respectively, elements of $A(j)$. Then $$\sum\_{j=0}^{k-1} \left(M(i)-m(i)\right)\geqslant 1+2+\ldots+(n-k),$$
since LHS equals to the sum of distances between adjacent equal elements, and there are at least $n-k$ such distances (exactly $n-k$ if $A(j)\ne \emptyset$ for all $j$). Since all guys $m(j)$ are distinct, their sum is at least $1+2+\ldots+k$, analogously the sum of $M(j)$ is at most $(n-k+1)+\ldots+n$, thus $$
\sum\_{j=0}^{k-1} M(i)-m(i)\leqslant (n-k+1)+\ldots+n-(1+\ldots+k)=k(n-k),$$
and we get $k(n-k)\geqslant 1+\ldots+n-k=(n-k)(n-k+1)/2$, or $n\leqslant 3k-1$.


Also we get that if $n=3k-1$ is the length of a suitable sequence $(a\_1,\ldots,a\_{3k-1})$, then this may be only possible if $a\_1,\ldots,a\_k$ are all distinct, and so are $a\_{2k-1},\ldots,a\_{3k-1}$. For $s=1,2,\ldots,2k-1$ denote by $f(i)$ the minimal positive number such that $a\_i=a\_{i+f(i)}$. Then $f(1),\ldots,f(2k-1)$ are well-defined and form a permutation of $1,\ldots,2k-1$. Also the numbers $i+f(i)$ must form a permutation of $k+1,\ldots,3k-1$. And if this all happens, we get $k!$ corresponding suitable sequences. It remains to note that then $(i-k,f(i)-k,2k-i-f(i))$ for $i=1,2,\ldots,2k-1$ are the columns of a $3\times (2k-1)$ zero-sum array (see definition at[A002074](http://oeis.org/A002047)), and viceversa.


