Without loss of generality we assume that $\sigma(1) \neq 1$. Also assume that $x_1 = x_2 = 1$. Let $k$ be the smallest natural number such that $\sigma^k(1) = 1$. And let $r$ be the smallest natural number such that $\sigma(x_i) = x_{i+r}$ for all $i = 1, 2, \dots, n$. Therefore $\sigma^k(x_i) = x_{i+kr}$. Since $x_1 = x_2 = 1$, it follows that $1+kr \equiv 1 \pmod{n^2}$, so $n^2$ divides $kr$. Further, it follows that $\sigma^k$ is the identity permutation. In fact, by looking at the pairs $(a, a)$ appearing in the sequence, it follows that for any $i$ and $1 \le j < k$ we have $\sigma^j(i) \neq i$. So $\sigma$ is made up of $n/k$ $k$-cycles. Let $l = n/k$. Without loss of generality, we can assume that $\sigma(i) = i+l$.

Consider $\{r, 2r, 3r, \dots, (k-1)r\} \pmod{n^2}$. Let $s$ be the smallest natural number such that $s \equiv jr \pmod{n^2}$. Replacing $\sigma$ by $\sigma^j$, we may assume that $s = r$. It then follows that $kr = n^2$, so $r = nl$.

For each $i = 1, 2, \dots, n^2$, let $a_i$ be an integer such that $0 \le a_i \le n-1$ and $a_i \equiv x_{i+1} - x_i \pmod{n^2}$. Note that for any $j = 0, 1, 2, \dots, n-1$, there exists exactly $n$ values of $i$ for which $a_i = j$. Since $\sigma(i) = i+l$, it follows that $a_{i+r} = a_i$. Therefore for any $j = 0, 1, 2, \dots, n-1$, there exists exactly $l$ values of $i$ with $1 \le i \le r$ and $a_i = j$. Hence we get $l = x_{r+1} - x_1 \equiv \sum_{i=1}^r a_i \equiv \ln(n-1)/2 \pmod{n}$. If $n$ is odd then it follows that $l = n$. If $n$ is even, then we have $n/2$ divides $l$. In this case, if $l$ is even then again $l = n$. Since $k > 1$, it follows that $l < n$ and hence $n \equiv 2 \pmod{4}$.