A harbour's tide gauge logged the water level once an hour for a year: levels[h] is hour h's reading. Boat owners ask: "between hours a and b, how big was the swing from lowest to highest water?"
Write tide_swings(levels, queries) -> list[int]. For each (a, b) with a <= b, answer max(levels[a..b]) - min(levels[a..b]) (inclusive), 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
Up to 10**5 readings (integers, possibly negative) and 10**5 queries.
⭐ Bonus: scanning each range still passes; a speed test with 10**5 queries over 10**5 readings earns a star for an O(n log n) build and O(1) per query.
Show hint
two sparse tables, for min and max. For length L, take k = L.bit_length() - 1; the windows [a, a + 2**k) and (b - 2**k, b] overlap but cover a .. b, and overlap doesn't matter for min or max.