Range Sum

Given an integer array arr and a closed interval [lower, upper], count how many contiguous non-empty subarrays have an element sum within the interval. Equal subarrays are counted separately by start and end positions. The fixed source's second example output is corrected from 8 to 13; the basis is in the notes.

输入格式

The first line contains n (1≤n≤50000); the second line contains n 32-bit signed integers; the third line contains lower upper (both 32-bit signed integers with lower≤upper).

输出格式

Output the number of contiguous subarrays whose sum lies in the closed interval [lower, upper].

样例 1

输入：

3
-2 5 -1
-2 2

输出：

3

样例 2

输入：

7
1 -3 5 2 5 2 -5
-2 6

输出：

13

样例 3

输入：

8
1 -3 5 -2 2 5 -1 10
5 9

输出：

12

样例说明

Use prefix sums to turn a range sum into the difference of two prefix sums, then count in O(n log n) time with merge sort and two pointers. The source output of the second public example was mistakenly written as 8; enumerating directly by definition gives 13.