500. Count of Pairs with Sum in a Range

Given two arrays a and b and a range [lo, hi], count the number of pairs (i, j) such that lo <= a[i] + b[j] <= hi. Use binary search over the sorted second array. The input is JSON {a, b, lo, hi}. Return the count.

Input: JSON {a, b, lo, hi}.

Output: Integer — the number of qualifying pairs.

Examples

Input: {"a":[1,2,3],"b":[4,5,6],"lo":5,"hi":8}
Output: 8
Explanation: 8 pairs have sum in [5,8].

Input: {"a":[1],"b":[1],"lo":2,"hi":2}
Output: 1
Explanation: Sum 2 is in range.

Input: {"a":[0,1,2],"b":[0,1,2],"lo":0,"hi":1}
Output: 6
Explanation: Six low-sum pairs.

Constraints

• 1<=len(a),len(b)<=10^4
• -10^9<=value,lo,hi<=10^9

Asked by