Count Pairs Below Threshold

Easy

You are given an integer array nums containing n elements (0-indexed) and an integer threshold . Your task is to determine how many index pairs (i, j) exist such that: The first index is strictly smaller than the second index: 0 \leq i < j < n The sum of the elements at these indices is strictly less than the threshold: nums[i] + nums[j] < threshold Return the total count of all such valid pairs that satisfy both conditions. Key Observations: Each pair is counted only once; specifically, if (i, j) is valid, we do not also count (j, i) because we require i < j . The same element can participate in multiple valid pairs with different partners. Both the array elements and the threshold can be negative, zero, or positive.

Example 1

Input

nums = [-1,1,2,3,1]
threshold = 2

Output

Explanation

There are 3 pairs of indices that satisfy both conditions: - Pair (0, 1): indices 0 < 1, and nums[0] + nums[1] = -1 + 1 = 0 < 2 ✓ - Pair (0, 2): indices 0 < 2, and nums[0] + nums[2] = -1 + 2 = 1 < 2 ✓ - Pair (0, 4): indices 0 < 4, and nums[0] + nums[4] = -1 + 1 = 0 < 2 ✓ Note that pair (0, 3) is not counted because nums[0] + nums[3] = -1 + 3 = 2, which is not strictly less than the threshold of 2.

Example 2

Input

nums = [-6,2,5,-2,-7,-1,3]
threshold = -2

Output

Explanation

There are 10 pairs whose sum is strictly below -2: - (0,1): -6 + 2 = -4 < -2 ✓ - (0,3): -6 + (-2) = -8 < -2 ✓ - (0,4): -6 + (-7) = -13 < -2 ✓ - (0,5): -6 + (-1) = -7 < -2 ✓ - (0,6): -6 + 3 = -3 < -2 ✓ - (1,4): 2 + (-7) = -5 < -2 ✓ - (3,4): -2 + (-7) = -9 < -2 ✓ - (3,5): -2 + (-1) = -3 < -2 ✓ - (4,5): -7 + (-1) = -8 < -2 ✓ - (4,6): -7 + 3 = -4 < -2 ✓

Example 3

Input

nums = [1,2,3,4,5]
threshold = 5

Output

Explanation

Only 2 pairs have sums strictly below the threshold of 5: - (0,1): 1 + 2 = 3 < 5 ✓ - (0,2): 1 + 3 = 4 < 5 ✓ All other pairs produce sums that are greater than or equal to 5.

Constraints

1 ≤ nums.length ≤ 50
-50 ≤ nums[i] ≤ 50
-50 ≤ threshold ≤ 50