Несложно заметить, что нам достаточно хотя бы $\lfloor \frac{n}{k} \rfloor$ чётных чисел. В таком случае мы расставим их на позиции $k, 2k, \ldots, \lfloor \frac{n}{k} \rfloor k$, а остальные числа расставим как угодно.

Асимптотика решения: $O(n)$.
