Count Contiguous Subarrays with Given Sum

You are given an array of integers and an integer target. Your task is to determine the number of contiguous subarrays that sum exactly to the target value.

Formally, given an integer array \(a_1, a_2, \dots, a_n\) and an integer \(T\), count the number of subarrays \(a_i, a_{i+1}, \dots, a_j\) such that \[ \sum_{k=i}^{j} a_k = T. \]

This problem requires an efficient solution. A typical approach is to use a cumulative sum (prefix sum) technique combined with a hash map to keep track of frequencies of prefix sums. Note that the array may contain negative numbers.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains a single integer \(n\), the size of the array.
• The second line contains \(n\) space-separated integers representing the elements of the array.
• The third line contains a single integer \(T\), the target sum.

outputFormat

Output to standard output (stdout) a single integer representing the number of contiguous subarrays whose elements sum to \(T\).

## sample

5
1 2 3 4 2
6

2

</p>