Subarray Sum RangesHard

Subarray Sum Ranges

Hard+60 XP · +20 Aurasliding windowprefix sumsfenwick tree

UptoSkills Arena is organizing a coding contest! We need to find the number of subarrays whose sum falls within a given range [A, B]. A subarray is a contiguous part of an array.

Given an array of integers arr and two integers A and B, count how many subarrays arr[i..j] (inclusive) satisfy A <= sum(arr[i..j]) <= B.

Input

The first line contains an integer N, the size of the array. The second line contains two integers A and B. The third line contains N space-separated integers, the elements of the array arr.

Output

Print a single integer, the total count of subarrays whose sum is between A and B (inclusive).

Constraints

1 <= N <= 200000 -10^9 <= A, B <= 10^9 -10^9 <= arr[i] <= 10^9

Time limit 2 s (native code; slower languages get more)Memory 256 MB16 hidden tests

Example 1

Input
4
1 3
1 -1 2 1
Output
8

Subarrays: [1] (sum 1), [-1, 2] (sum 1), [2] (sum 2), [1] (sum 1), [1, -1, 2] (sum 2), [-1, 2, 1] (sum 2), [2, 1] (sum 3). Total 7 subarrays.

Example 2

Input
3
-2 2
1 -2 1
Output
6

Subarrays: [1] (sum 1), [-2] (sum -2), [1] (sum 1), [1, -2] (sum -1), [-2, 1] (sum -1), [1, -2, 1] (sum 0). Total 6 subarrays.

Hints