120. Count of Range Sum

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. A range sum S(i,j) is the sum of nums[i..j] for i<=j. Input: '[nums], lower, upper'.

Input: '[nums], lower, upper'.

Output: Integer count.

Examples

Input: [-2,5,-1], -2, 2
Output: 3
Explanation: Range sums in [-2,2]: [0,0]=-2,[2,2]=-1,[0,2]=2.

Input: [0], 0, 0
Output: 1
Explanation: Single range sum 0.

Input: [1,2,3], 3, 6
Output: 4
Explanation: Four range sums in [3,6].

Constraints

• 1<=n<=10^5
• -2^31<=nums[i]<=2^31-1
• -10^5<=lower<=upper<=10^5

Asked by