Find the Smallest Stable Index II

# Find the Smallest Stable Index II You are given an integer array `nums` of length `n` and an integer `k`. For each zero-based index `i`, its instability score is: `max(nums[0..i]) - min(nums[i..n - 1])`. Both ranges are inclusive: the prefix ends at `i` and the suffix begins at `i`, so `nums[i]` belongs to both. Return the smallest index whose score is at most `k`. If no such index exists, return `-1`. ### Function `int firstStableIndex(vector<int>& nums, int k)` ### Example 1 **Input:** `nums = [4, 9, 1, 8, 10], k = 2` **Output:** `3` **Explanation:** The prefix maxima are `[4, 9, 9, 9, 10]`, and the suffix minima are `[1, 1, 1, 8, 10]`. Their differences are `[3, 8, 8, 1, 0]`. The first score at most `2` occurs at index `3`. ### Example 2 **Input:** `nums = [1000000000, 0, 1000000000], k = 0` **Output:** `2` **Explanation:** The first two scores are `1000000000`. At index `2`, the prefix maximum and suffix minimum both equal `1000000000`, so the score is `0` and qualifies. ### Constraints - `1 <= nums.length <= 100000` - `0 <= nums[i] <= 1000000000` - `0 <= k <= 1000000000` ### Clarifications - Return a zero-based index. - A score equal to `k` is stable, and values in the array may repeat. - The array's original order defines the ranges; the task does not allow rearranging its values. ### What a Strong Answer Covers - Using the exact inclusive ranges at every candidate index. - Returning the smallest qualifying index, including when several qualify. - Supporting `100000` elements without rescanning the entire array for every index.