Solution: It is possible if and only if $n$ is odd.
If $n$ is even, then $a_1 + a_2 + \dots + a_n = 1 + 2 + \dots + n = \frac{n}{2} \cdot (n + 1)$, which is congruent to $0$ mod $n + 1$. Therefore, the task is impossible.

Now suppose $n$ is odd. We will show that we can construct $a_1, a_2, \dots, a_n$ that satisfy the conditions given in the problem. Then let $n = 2k + 1$ for some non-negative integer $k$. Consider the sequence: $1, 2k, 3, 2k-2, 5, 2k-3, \dots, 2, 2k+1$, i.e. for each $1 \le i \le 2k+1$, $a_i = i$ if $i$ is odd and $a_i = 2k+2-i$ if $i$ is even.

We first show that each term $1, 2, \dots, 2k+1$ appears exactly once. Clearly, there are $2k+1$ terms. For each odd number $m$ in $\{1, 2, \dots, 2k+1\}$, $a_m = m$. For each even number $m$ in this set, $a_{2k+2-m} = 2k+2-(2k+2-m)=m$. Hence, every number appears in $a_1, \dots, a_{2k+1}$. Hence, $a_1, \dots, a_{2k+1}$ does consist of the numbers $1, 2, \dots, 2k+1$ in some order.

We now determine $a_1 + a_2 + \dots + a_m \pmod{2k+2}$. We will consider the cases when $m$ is odd and when $m$ is even separately. Let $b_m = a_1 + a_2 + \dots + a_m$.

If $m$ is odd, note that $a_1 \equiv 1 \pmod{2k+2}$, $a_2 + a_3 = a_4 + a_5 = \dots = a_{2k} + a_{2k+1} = 2k+3 \equiv 1 \pmod{2k+2}$. Therefore, $\{b_1, b_3, \dots, b_{2k+1}\} = \{1, 2, 3, \dots, k+1\} \pmod{2k+2}$.

If $m$ is even, note that $a_1 + a_2 = a_3 + a_4 = \dots = a_{2k-1} + a_{2k} = 2k+1 \equiv -1 \pmod{2k+2}$. Therefore, $\{b_2, b_4, \dots, b_{2k}\} = \{-1, -2, \dots, -k\} \pmod{2k+2} \equiv \{2k+1, 2k, \dots, k+2\} \pmod{2k+2}$.

Therefore, $b_1, b_2, \dots, b_{2k+1}$ do indeed have different remainders when divided by $2k+2$. This completes the problem. $\square$