Minimum Travel Cost Between Array Indices

# Minimum Travel Cost Between Array Indices You are given a strictly increasing integer array `nums` and a list of independent queries `queries`. For an index `x`, define `closest(x)` as whichever adjacent index has the smaller absolute difference from `nums[x]`. Only indices `x - 1` and `x + 1` are candidates when they exist. If both differences are equal, choose the smaller index. An endpoint has just one adjacent index. From your current index `x`, either move is allowed: - Move to any index `y`, paying `abs(nums[x] - nums[y])`. - Move to `closest(x)`, paying `1`. For each query `[l, r]`, find the minimum total cost to travel from index `l` to index `r`. Return the answers in query order. ### Function `vector<int> minCost(vector<int>& nums, vector<vector<int>>& queries)` ### Example 1 **Input:** `nums = [-8, -4, 0, 1, 7], queries = [[0, 4], [4, 0], [1, 3], [2, 2]]` **Output:** `[12, 7, 5, 0]` **Explanation:** The closest indices are `[1, 0, 3, 2, 3]`. At index `1`, the two neighboring differences both equal `4`, so index `0` wins the tie. - From `0` to `4`, following `0 -> 1 -> 2 -> 3 -> 4` costs `1 + 4 + 1 + 6 = 12`. - From `4` to `0`, following `4 -> 3 -> 2 -> 1 -> 0` costs `1 + 1 + 4 + 1 = 7`. - From `1` to `3`, the minimum cost is `4 + 1 = 5`. - Staying at index `2` costs `0`. ### Example 2 **Input:** `nums = [-100, 100], queries = [[0, 1], [1, 0], [0, 0]]` **Output:** `[1, 1, 0]` **Explanation:** Each index has only the other index as its neighbor. The special move costs `1` in either direction, even though their values differ by `200`. ### Constraints - `2 <= nums.length <= 100000` - `-1000000000 <= nums[i] <= 1000000000` - `nums` is strictly increasing. - `1 <= queries.length <= 100000` - Each query contains exactly two indices `[l, r]` with `0 <= l, r < nums.length`. ### Clarifications - All indices are zero-based. A query may start and end at the same index. - The closest neighbor is determined by the fixed array, independently of the query destination. - A trip may use any number of moves and combine both move types. - Travel costs can differ between the two directions. ### What a Strong Answer Covers - Applying the smaller-index tie rule and endpoint rule exactly. - Finding the minimum over all allowed trips, including trips with ordinary jumps. - Answering the full query limit while preserving query order.