Областная олимпиада по математике 2004 года за 9 класс | Казахстанские олимпиады

Даны числа 1, 1, 2, 2, 3, 3, $\dots$, $n$, $n$. При каких значениях $n$ эти числа можно так объединить в $n$ пар, чтобы сумма чисел, стоящих в каждой паре, давали при делении на $n$ различные остатки?