Subarrays with Sum K

Hard#arrays #prefix-sums #hashing· solved by 0 · time limit 2.0 s

Count the contiguous subarrays whose sum is exactly $k$ . Values can be negative, so a sliding window doesn't work — combine prefix sums with a hash map.

Input

$n$ , then $n$ integers, then $k$ .

Output

The number of subarrays.

Constraints

$1 \le n \le 2 \times 10^5$ , $|a_i| \le 10^4$

Sample 1

Input

3
1 1 1
2

Output

Sample 2

Input

3
1 2 3
3

Output