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

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, các phần tử có thể âm, bằng $0$ hoặc dương, cùng một số nguyên $x$.

Hãy đếm số đoạn con liên tiếp không rỗng có tổng đúng bằng $x$.

Một đoạn con được xác định bởi hai chỉ số đầu-cuối $(l,r)$ với $1\le l\le r\le n$.

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$

• $-10^9\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 -1 3 5 -2

Output

2

Giải thích

Với dãy

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

• $[1,5]$: $2-1+3+5-2=7$;
• $[2,4]$: $-1+3+5=7$.

Không còn đoạn nào khác có tổng bằng $7$, nên kết quả là $2$.