454. Count Pairs Whose Sum is Less Than Target

Given a sorted array nums and an integer target, count the number of pairs (i, j) with i < j such that nums[i] + nums[j] < target.

Input: A sorted integer array nums and integer target.

Output: Count of valid pairs.

Examples

Example 1

Input: [-1,1,2,3,5], 4
Output: 3
Explanation: Pairs: (-1,1)=0, (-1,2)=1, (-1,3)=2, (-1,5)=4✗, (1,2)=3, ... valid: (-1,1),(-1,2),(1,2). Count=3.

Example 2

Input: [1,2,3,4,5], 8
Output: 6
Explanation: All pairs with sum<8: (1,2),(1,3),(1,4),(1,5),(2,3),(2,4). Count=6.

Example 3

Input: [1,2,3,4,5], 2
Output: 0
Explanation: Min sum=1+2=3>=2. No valid pairs.