Three. (50 points) Find all positive integers $n$, for which there exists a permutation of 1, 2, $\cdots, n$ such that $\left|a_{i}-i\right|$ are all distinct.

Find all positive integers $n$, for which there exists a permutation of 1, 2, $\cdots, n$ such that $\left|a_{i}-i\right|$ are all distinct.
$$
\begin{array}{l}
\text { Let } a_{1}, a_{2}, \cdots, a_{n} \text { be a permutation with the given property, then } \\
\left\{\left|a_{1}-1\right|,\left|a_{2}-2\right|,\left|a_{3}-3\right|, \cdots,\left|a_{n}-n\right|\right\}= \\
\{0,1,2, \cdots, n-1\} \\
\sum_{k=1}^{n}\left|a_{k}-k\right|=\frac{1}{2} n(n-1), \\
\text { and } \sum_{k=1}^{n}\left|a_{k}-k\right| \equiv \sum_{k=1}^{n}\left(a_{k}-k\right) \equiv 0(\bmod 2) \\
\therefore \frac{1}{2} n(n-1) \equiv 0(\bmod 2) \\
\therefore n=4 k \text { or } 4 k+1 .
\end{array}
$$

Construction:
$$
\begin{array}{l}
\quad n=4 k \text {, } \\
\quad n: 1,2,3, \cdots, k, k+1, k+2, \cdots, 2 k, 2 k+1,2 k+ \\
2, \cdots, 3 k, 3 k+1,3 k+2, \cdots, 4 k-1,4 k, a n: 2 k+1,4 k, \\
4 k-1, \cdots, 3 k+2, k+1,3 k+1, \cdots, 2 k+3,2 k+2,2 k, \\
\cdots, k+2, k, k-1, \cdots, 2,1,\left|a_{n}-n\right|: 2 k, 4 k-2,4 k- \\
4, \cdots, 2 k+2,0,2 k-1, \cdots, 3,1,2, \cdots, 2 k-2,2 k+1, \\
2 k+3, \cdots, 4 k-3,4 k-1 ; \\
\quad n=4 k+1 \text {, } \\
\quad n: 1,2,3, \cdots, k, k+1, k+2, \cdots, 2 k, 2 k+1,2 k+ \\
2, \cdots, 3 k, 3 k+1,3 k+2, \cdots, 4 k-1,4 k, 4 k+1, \\
a_{n}: 2 k+2,4 k+1,4 k, \cdots, 3 k+3, k+1,3 k+2, \\
\cdots, 2 k+4,2 k+3,2 k+1, \cdots, k+3, k+2, k, \cdots, 3,2, \\
1,\left|a_{n}-n\right|: 2 k+1,4 k-1,4 k-3, \cdots, 2 k+3,0,2 k, \\
\cdots, 4,2,1, \cdots, 2 k-3,2 k-1,2 k+2, \cdots 4 k-4,4 k-2,
\end{array}
$$
$4 k$.