AUSTRIAN-POLISH 1990 Problem 5

Let $n>1$ be an integer and let $f_1$ , $f_2$ , ..., $f_{n!}$ be the $n!$ permutations of $1$ , $2$ , ..., $n$ . (Each $f_i$ is a bijective function from $\{1,2,...,n\}$ to itself.) For each permutation $f_i$ , let us define $S(f_i)=\sum^n_{k=1} |f_i(k)-k|$ . Find $\frac{1}{n!} \sum^{n!}_{i=1} S(f_i)$ .