BALKAN 2025 Problem 1

An integer $n > 1$ is called good if there exists a permutation $a_{1},a_{2},a_{3},\ldots ,a_{n}$ of the numbers $1,2,3,\ldots ,n$ , such that:

• $a_{i}$ and $a_{i + 1}$ have different parities for every $1 \leqslant i \leqslant n - 1$ ;

• the sum $a_{1} + a_{2} + \dots + a_{k}$ is a quadratic residue modulo $n$ for every $1 \leqslant k \leqslant n$ .

Prove that there exist infinitely many good numbers, as well as infinitely many positive integers which are not good.

Remark: Here an integer $x$ is considered a quadratic residue modulo $n$ if there exists an integer $y$ such that $x \equiv y^{2} \pmod {n}$ .