The smallest in a range

Return a list with the smallest value of a[l:r] for each query (l, r). The list a never changes, and every range has at least one value.

range_min([5, 2, 7, 4, 6, 1, 8, 3],
          [(1, 7), (2, 5), (0, 1), (6, 8)])
# [1, 4, 5, 3]

Every range is half-open, as in Python slices: (l, r) means positions l up to but not including r, the same values as a[l:r].

One test passes in numbers that count how often they are compared with <, <=, > or >= (min and max compare too). They behave like ordinary numbers otherwise. This is how the tests tell the method apart from slower ones, which a timer cannot always do.

Limits

• Up to 100,000 values and 100,000 queries. Build in O(n log n), then answer each query with O(1) comparisons: at most n log₂ n + 2q comparisons in all for q queries.