An $n$-tuple $(a_1, a_2 . . . , a_n)$ is occasionally periodic if there exist a non-negative integer $i$ and a positive integer $p$ satisfying $i + 2p \le n$ and $a_{i+j} = a_{i+j+p}$ for every $j = 1, 2, . . . , p$. Let $k$ be a positive integer. Find the least positive integer $n$ for which there exists an $n$-tuple $(a_1, a_2 . . . , a_n)$ with elements from the set $\{1, 2, . . . , k\}$, which is not occasionally periodic but whose arbitrary extension $(a_1, a_2, . . . , a_n, a_{n+1})$ is occasionally periodic for any $a_{n+1} \in \{1, 2, . . . , k\}$.