합이 K인 부분 배열의 개수

제한

• $1 \le N \le 10^5$
• $1 \le A_i \le 10^9$
• $1 \le K \le 10^{14}$

입출력 예시

입력 1

5 9
1 2 3 4 5

출력 1

2

설명: 위 그림의 예와 같이 $\{2, 3, 4\}$와 $\{4, 5\}$ 두 개가 답이다.

입력 2

6 10
2 1 4 3 5 1

출력 2

1

설명: 합이 10인 연속 부분 배열은 $\{2, 1, 4, 3\}$ ($l=0, r=3$) 하나뿐이다.

입력 3

4 7
1 1 1 1

출력 3

0

설명: 전체 합이 4뿐이라 7이 되는 부분 배열이 없다.

풀이 힌트

투 포인터를 모르면 모든 $(l, r)$ 쌍을 시도해 $O(N^2)$가 된다. $N = 10^5$이면 시간 안에 못 푼다. 투 포인터로 에 풀어 본다. 합이 64비트 범위를 쉽게 넘기니 을 쓴다.