A harbour's tide gauge logged the water level (in centimetres) once an hour for a whole year: levels[h] is the reading at hour h. The log never changes. Boat owners keep asking the harbour master: "between hour a and hour b, how big was the swing from the lowest to the highest water?"
Write tide_swings(levels, queries) -> list[int]. Each query is a pair (a, b) with a <= b; its answer is max(levels[a..b]) - min(levels[a..b]) (both ends inclusive). Return the answers in query order.
levels = [120, 180, 240, 210, 130, 60, 90]
tide_swings(levels, [(0, 2), (2, 5), (3, 3), (0, 6)])
# [120, 180, 0, 180]
# (0,2): 240 - 120 (2,5): 240 - 60 (3,3): one reading (0,6): 240 - 60
Constraints: 1 <= len(levels) <= 10**5, 0 <= a <= b < len(levels), up to 10**5 queries, levels are integers with -10**6 <= level <= 10**6 (they can be negative near low spring tides). Scanning each range is O(n) per query, around 10**10 steps; after an O(n log n) build, each query must be O(1).
Show hint
build two sparse tables, one for minimums and one for maximums. For a query of length L, let k be the largest power with 2**k <= L (L.bit_length() - 1); the two windows [a, a + 2**k) and (b - 2**k, b] overlap but together cover a .. b exactly, and overlapping doesn't matter for min or max.