Đếm đoạn con có tổng X I (Subarray Sums I)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một mảng gồm $n$ số nguyên dương và một số nguyên $x$.

Một đoạn con là một dãy các phần tử liên tiếp của mảng. Hãy đếm số đoạn con không rỗng có tổng đúng bằng $x$.

Hai đoạn được xem là khác nhau nếu cặp vị trí đầu và cuối của chúng khác nhau.

Input

• Dòng đầu chứa hai số nguyên $n,x$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$.

Output

In số đoạn con liên tiếp có tổng bằng $x$.

Subtask

Điều kiện chung đã đối chiếu với nguồn:

• $1\le n\le2\cdot10^5$

• $1\le x,a_i\le10^9$

• Subtask 1 — 20%: $n\le40$

• Subtask 2 — 30%: $n\le3000$.

• Subtask 3 — 50%: không có điều kiện bổ sung ngoài các điều kiện chung ở trên.

Ví dụ

Input

5 7
2 4 1 2 7

Output

3

Giải thích

Với dãy

và $x=7$, có ba đoạn thỏa mãn:

• $[1,3]$: $2+4+1=7$;
• $[2,4]$: $4+1+2=7$;
• $[5,5]$: phần tử duy nhất bằng $7$.

Vì vậy đáp án là $3$.