1. There are n! kinds of paths, ie. n * n! pairs.
2. For each a_i there are (n - 1)! times being the last one(appear once), And n! - (n - 1)! times appear twice,
3. Thus a number a_i appear 2 * (n! - (n - 1)!) + (n - 1)! = 2 * n! - (n - 1)! times.
4. Realize that among all paths, except for the first row, ie. |0 - a_i|, each pair appears (n * n! - (n - 1)!) / C(n, 2) = 2 * (n - 1)! times.
5. Assume that the squence is sorted in ascending order. has i elements less than it. Hence, include the first row it has i * 2 * (n - 1)! + (n - 1)! = (2 * i + 1) * (n - 1)! times to be positive, and has 2 * n! - (n - 1)! - (2 * i + 1)(n - 1)! = 2 * n! - (2 * i + 2) * (n - 1)! to be negative.
6. Thus, for each a_i, include 1st row, the sum of it in all paths is

7, Average for a_i's sum is

1. Finnally, we got the result: