3 Let $a_{1}, a_{2}, \cdots, a_{n}$ be a permutation of $1,2, \cdots, n$, find the maximum value of $S_{n}=\left|a_{1}-1\right|+\mid a_{2}-$ $2|+\cdots+| a_{n}-n \mid$.
3. The key to solving the problem is to remove the absolute value symbol. Note that $\left|a_{i}-i\right|$ equals $a_{i}-i$ or $i-a_{i}$, so after removing the absolute value symbol, the number of negative signs in the sum remains unchanged. That is, regardless of how $a_{1}, a_{2}, \cdots, a_{n}$ are arranged, after removing the absolute value symbol, the sum always has $n$ negative signs. Thus, when $n$ is even, $S_{n} \leqslant n+n+(n-1)+(n-1)+\cdots+\left(\frac{n}{2}+1\right)+\left(\frac{n}{2}+1\right)-\frac{n}{2}-\frac{n}{2}-\cdots-1-1=\frac{n^{2}}{2}$. When $n$ is odd, a similar result can be obtained. In summary, $S_{n} \leqslant\left[\frac{n^{2}}{2}\right]$. Furthermore, when $\left(a_{1}, a_{2}, \cdots, a_{n}\right)=(n, n-1, n-2, \cdots, 2,1)$, $S_{n}=\left[\frac{n^{2}}{2}\right]$. Therefore, the maximum value of $S_{n}$ is $\left[\frac{n^{2}}{2}\right]$.