A hiking trail has checkpoints 0, 1, ..., n - 1 in a line, and heights[i] is the elevation of checkpoint i in metres. Hikers walk the trail in either direction, and their fitness app only counts climbing: every step between neighbouring checkpoints that goes up adds the height difference, and every step that goes down adds nothing.
Write uphill(heights: list[int], trips: list[tuple[int, int]]) -> list[int]. Each trip (a, b) walks from checkpoint a straight to checkpoint b (so towards higher indexes if a < b, towards lower ones if a > b). Return the metres climbed on each trip, in order.
Example: from checkpoint 4 back to 0 the steps are 150 -> 160 (+10), 160 -> 120 (down), 120 -> 130 (+10), 130 -> 100 (down), so that trip climbs 20 metres, while 0 -> 4 climbs 30 + 40 = 70:
uphill([100, 130, 120, 160, 150], [(0, 4), (4, 0), (1, 3), (2, 2)]) # [70, 20, 40, 0]
uphill([5, 5, 5], [(0, 2), (2, 0)]) # [0, 0]
Constraints: up to 10^5 checkpoints and 10^5 trips, elevations between -10^9 and 10^9 (some trails go below sea level). Walking every trip step by step is O(n) per trip and too slow for the large test.
Show hint
build two prefix arrays, one adding up only the rises max(0, heights[i+1] - heights[i]) and one adding up only the drops; a forward trip reads the rises between a and b, and a backward trip reads the drops, because a drop walked backwards is a climb.