USAMO 2007 Problem 1

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$ , letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$ . For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$ . Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.