How many subarrays sum up to X?
Given an array of
n positive integers, you are asked to calculate the number of subarrays that sum up to exactly X. A subarray is a contiguous portion of an array. It is a subset of the original array, consisting of one or more adjacent elements of the original array.Input
The first line of the input contains an integer
n (1 ≤ n ≤ ).The next line contains
n space-separated integers (1 ≤ ≤ ).The third line contains the target integer
X (1 ≤ X ≤ ).Output
The program should print the number of subarrays that sum up to
X.Examples
Input | Output |
5
1 7 1 2 6
8 | 3 |
Explanation
1 7 1 2 6, 1 7 1 2 6, 1 7 1 2 6Constraints
Time limit: 3 seconds
Memory limit: 512 MB
Output limit: 1 MB