Algorithms and Data Structures

• Status
• 1
Implementation
• 2
Bitwise operations
• 3
Prefix Sums
• 4
Sliding window / Two pointers
• 5
Modular Arithmetic
• 6
Number Theory
• 7
Binary Search
• 8
Basic Sorting
• 9
Greedy Algorithms
• 10
Basic Dynamic Programming
• 11
Recursion
• 12
• 13
Queue & Stack
• 14
Binary tree + BST
• 15
Divide & Conquer + Advanced Sorting
• 16
Heap
• 17
Hashing
• 18
Graph Representation
• 19
BFS

• # 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 6`

#### Constraints

Time limit: 3 seconds

Memory limit: 512 MB

Output limit: 1 MB