This problem (reportedly) took Don Knuth, 24 hours to solve

I don't know what was Knuth's solution, but it's trivial:

   (- (reduce '+ vector)
      (let ((n (- (length vector) 2)))
        (/ (* n (+ n 1)) 2)))

reduce is O(n) time and O(1) space. length is O(1) time and space.

Notice also that if there are no duplicates, this formula will give the maximum element (- (length vector) 1).