A treasury ledger records n daily net movements (credits positive, debits negative). An auditor wants to know how many contiguous runs of days have a net total that lands inside an inclusive band [lo, hi].
Count the contiguous runs (subarrays) whose sum S satisfies lo <= S <= hi. The intended approach builds prefix sums and, during a merge sort of those prefix sums, counts qualifying pairs whose difference lies in the band.
Input format
Line 1: three integers n, lo, hi (with lo <= hi).
Line 2: n space-separated integers, the daily net movements.
Output format
A single integer: the number of contiguous runs whose sum lies in [lo, hi].
Constraints
- 1 <= n <= 100000
- -1000000000 <= each movement <= 1000000000
- -1000000000000000 <= lo <= hi <= 1000000000000000