Solution:

For $n \leqslant 28$ the condition of the problem is satisfied only for $n \in\{2,4,10\}$. Let $n>28$. Notice that the sequence $a_{i}$ is symmetric with respect to $\frac{n}{2}$. Thus $a_{i}+a_{k+1-i}=n$. If $2 \nmid n$, then $a_{1}=1, a_{2}=2$ and $3 \mid a_{1}+a_{2}$. On the other hand, if $3 \mid n$, choose $i$ such that $a_{i}<\frac{n}{2}<a_{i+1}$: then $3 \mid a_{i}+a_{i+1}=n$. Further, $2 \mid n$ and $3 \nmid n$, so $a_{2}=3$. From this we also get $a_{k-1}=n-3$ and $a_{k}=n-1$.
If $n \equiv 2(\bmod 3)$, then $3 \mid a_{k-1}+a_{k}=2 n-4$. Only the case $n \equiv 1$ $(\bmod 3)$ remains.
Further, if $a_{i}+a_{i+1} \equiv 2(\bmod 3)$, then $a_{k-i}+a_{k+1-i}=2 n-\left(a_{i}+a_{i+1}\right) \equiv 0(\bmod 3)$. Therefore we may assume that $a_{i}+a_{i+1} \equiv 1(\bmod 3)$ for $i=$ $1,2, \ldots, k-1$. By induction we find
$$a_{1} \equiv a_{3} \equiv \cdots \equiv 1 \quad \text { and } \quad a_{2} \equiv a_{4} \equiv \cdots \equiv 0 \quad(\bmod 3)$$
Since $(n, 9)=1$, it follows that $a_{4}=9$, and since $a_{3} \equiv 1(\bmod 3)$ we also have $a_{3}=7$. From this we obtain $(n, 7)=1$ and $(n, 5) \neq 1$, i.e. $5 \mid n$.
Now we have $(n, 21)=(n, 27)=1$, but the numbers $22,24,25$ and 26 are not relatively prime to $n$, and by $(*)$ the number 23 also cannot occur in the sequence $a_{1}, \ldots, a_{k}$. Thus 21 and 27 are neighbors in the sequence $a_{1}, \ldots, a_{k}$, but $3 \mid 21+27$, a contradiction.
Therefore, the only solutions are 2, 4 and 10.