Given a list of integers nums sorted in non-decreasing order and two integers lo <= hi, return the number of index pairs (i, j) with i < j such that lo <= nums[i] + nums[j] <= hi.
Examples
Input: nums = [1, 2, 3, 4, 5], lo = 5, hi = 6
Output: 4
Explanation: (1,4), (1,5), (2,3), (2,4) have sums 5, 6, 5, 6.
Input: nums = [-2, 0, 1, 3], lo = -1, hi = 1
Output: 3
Explanation: -2+1 = -1, -2+3 = 1 and 0+1 = 1 are inside the range.
Constraints
0 <= len(nums) <= 10**5, values fit in a Python int-10**9 <= lo <= hi <= 10**9- Target: O(n) time, O(1) extra space (no nested loops over pairs).
Goals
- Count all pairs below a bound in one converging scan
- Turn a range query into a difference of two prefix-style counts