Since $\{a_{1}, a_{2}, \ldots, a_{n}\}=\{1,2, \ldots, n\}$ we conclude that $a_{i}-a_{j}$ : $n$ only if $i=j$. From the problem conditions it follows that $$a_{k+1}=a_{k}^{2}+\varepsilon_{k}-n b_{k}$$ where $b_{k} \in \mathbb{Z}$ and $\varepsilon_{k}= \pm 1$. We have $a_{k+1}-a_{l+1}=\left(a_{k}-a_{l}\right)\left(a_{k}+a_{l}\right)+\left(\varepsilon_{k}-\varepsilon_{l}\right)-n\left(b_{k}-b_{l}\right)$. It follows that if $a_{k}+a_{l}=n$ then $\varepsilon_{k} \neq \varepsilon_{l}$ otherwise $a_{k+1}-a_{l+1} \vdots n$ - contradiction. The condition $\varepsilon_{k} \neq \varepsilon_{l}$ means that $\varepsilon_{k}=-\varepsilon_{l}$. Further, one of the $a_{i}$ equals $n$. Let, say, $a_{m}=n$. Then the set $\{a_{1}, a_{2}, \ldots, a_{n}\} \backslash\{a_{m}\}$ can be divided into $\frac{n-1}{2}$ pairs $\left(a_{k}, a_{l}\right)$ such that $a_{k}+a_{l}=n$. For any such pairs of indices $k, l$ we have $\varepsilon_{k}+\varepsilon_{l}=0$. Now add all the equalities for $k=1,2, \ldots, n$. Then $\sum_{k=2}^{n+1} a_{k}=\sum_{k=1}^{n} a_{k}^{2}-n \sum_{k=1}^{n} b_{k}+\varepsilon_{m}$, or $1+2+\ldots+n=1^{2}+2^{2}+\ldots+n^{2}-n \sum_{k=1}^{n} b_{k}+\varepsilon_{m}$ whence $$n \sum_{k=1}^{n} b_{k}=\frac{n(n+1)(2 n+1)}{6}-\frac{n(n+1)}{2}+\varepsilon_{m}=\frac{n(n+1)(n-1)}{3}+\varepsilon_{m}$$ Note that if $n$ is not divisible by 3 then the number $\frac{n(n+1)(n-1)}{3}$ is divisible by $n$ (since $\frac{(n+1)(n-1)}{3}$ is integer). It follows that $\varepsilon_{m} \vdots n$ which is impossible. Hence $n$ is divisible by 3 and it follows that $\varepsilon_{m}$ is divisible by the number $\frac{n}{3}$. The latter is possible only for $n=3$ because $\varepsilon_{m}= \pm 1$. It remains to verify that $n=3$ satisfies the problem conditions. Indeed, let $a_{1}=1, a_{2}=2, a_{3}=3$. Then $a_{1}^{2}-a_{2}+1=0 \vdots 3, a_{2}^{2}-a_{3}-1=0 \vdots 3$ and $a_{3}^{2}-a_{1}+1=9 \vdots 3$.