Comment by BearsAreCool

With a linear time O(N) first pass you can identify the minimum element in the list. This reduces M from being the largest element to being the difference between the largest and the smallest element.