Contest Duration: - (local time) (100 minutes) Back to Home
D - Count Interval /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

A の連続部分列のうち、要素の和が K になるものはいくつありますか？
すなわち、以下の条件を全て満たす整数の組 (l,r) はいくつありますか？

• 1\leq l\leq r\leq N
• \displaystyle\sum_{i=l}^{r}A_i = K

### 制約

• 1\leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• |K| \leq 10^{15}
• 入力に含まれる値は全て整数である

### 入力

N K
A_1 A_2 \ldots A_N


### 入力例 1

6 5
8 -3 5 7 0 -4


### 出力例 1

3


(l,r)=(1,2),(3,3),(2,6)3 組が条件を満たします。

### 入力例 2

2 -1000000000000000
1000000000 -1000000000


### 出力例 2

0


Score : 400 points

### Problem Statement

Given is a sequence of length N: A=(A_1,A_2,\ldots,A_N), and an integer K.

How many of the contiguous subsequences of A have the sum of K?
In other words, how many pairs of integers (l,r) satisfy all of the conditions below?

• 1\leq l\leq r\leq N
• \displaystyle\sum_{i=l}^{r}A_i = K

### Constraints

• 1\leq N \leq 2\times 10^5
• |A_i| \leq 10^9
• |K| \leq 10^{15}
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N


### Sample Input 1

6 5
8 -3 5 7 0 -4


### Sample Output 1

3


(l,r)=(1,2),(3,3),(2,6) are the three pairs that satisfy the conditions.

### Sample Input 2

2 -1000000000000000
1000000000 -1000000000


### Sample Output 2

0


There may be no pair that satisfies the conditions.