Count Triples With Sum Below Target

You are given a list of integers nums and an integer target.

Return the number of index triples i < j < k such that nums[i] + nums[j] + nums[k] < target. The answer counts index triples, not distinct value combinations, so equal values at different indices count separately.

Examples

Example 1

Input: nums = [-2,0,1,3], target = 2
Output: 2
Explanation: The triples are (-2,0,1) with sum -1 and (-2,0,3) with sum 1, both less than 2.

Example 2

Input: nums = [1,1,1,1], target = 4
Output: 4
Explanation: There are four index triples here, one for each element left out. Every one of them sums to 3, which is less than 4, so all four count even though the values are identical.

Example 3

Input: nums = [5,6,7], target = 3
Output: 0
Explanation: The only triple has sum 18, which is not less than 3.