#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

Subarray Sum Equals K - Classic Problems | Repovive

CLS45. Subarray Sum Equals K

2s256 MB

Given an array of integers and a target value $k$ , count the number of non-empty contiguous subarrays whose sum is exactly $k$ .

Constraints

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le a_i, k \le 10^9$
The answer fits in a signed 64-bit integer.

Input

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

Output

count

Samples

Input

5 3
1 2 1 2 1

Explanation

There are four contiguous subarrays with total 3: positions 1..2, 2..3, 3..4, and 4..5.

Output

Input

4 0
0 0 0 0

Explanation

Every non-empty contiguous subarray has total 0, so all 10 subarrays count.

Output

Input

6 -1
2 -3 1 -1 2 -2

Explanation

The six qualifying segments are 1..2, 1..4, 1..6, 2..5, 4..4, and 4..6.

Output

Given an array of integers and a target value $k$ , count the number of non-empty contiguous subarrays whose sum is exactly $k$ .

$1 \le n \le 2 \cdot 10^5$
$-10^9 \le a_i, k \le 10^9$
The answer fits in a signed 64-bit integer.

\begin{array}{l} n \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_n \end{array}

count