합이 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

2

설명: $\{2, 1, 4, 3\}$ ($l=0, r=3$)과 \{4, 3, 5\}\를 제외하면... 잠깐, $2+1+4+3=10$, , 이렇게 2개. 정확히 과 .

입력 3

4 7
1 1 1 1

출력 3

0

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

풀이 힌트

투 포인터를 모르면 모든 $(l, r)$ 쌍을 시도해 $O(N^2)$가 된다. $N = 10^5$이면 시간 안에 못 푼다. 투 포인터로 에 풀자. 합이 매우 클 수 있으니 타입을 쓰자.