ISL 2008 C2

For every positive integer $n$ determine the number of permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of the set $\{1,2, \ldots, n\}$ with the following property: $$2\left(a_{1}+a_{2}+\cdots+a_{k}\right) \text { is divisible by } k \text { for } k=1,2, \ldots, n \text {. }$$