If you sort the elements first, you can get the runtime down to
`O(n log n)`

.

The idea here is that if `a[]`

is the list of integers in
sorted order and `b[i]`

is the sum of the differences between
`a[i]`

and the other numbers, then `b[i+1]`

can be
computed directly in terms of `b[i]`

, `i`

,
`a[i+1] - a[i]`

, and the length of the array.

I won't say exactly how, but here's a hint. How much can
`Math.abs(a[i+1] - a[j])`

differ from ```
Math.abs(a[i] -
a[j])
```

? For which `j`

is ```
Math.abs(a[i+1] -
a[j])
```

greater? For which `j`

is it smaller?

Now, after you compute those, the `b[i]`

s then among
themselves contain each difference twice. The value you want is just their
sum divided by 2.