합이 딱 맞는 배달 구간

문제

우체국이 담당하는 거리에는 구역이 일렬로 N개 늘어서 있다. 오늘 하루 동안 i번째 구역에서는 우편물이 a_i개만큼 순증가했다. 수신량이 발송량보다 많으면 a_i가 양수이고, 발송량이 더 많으면 음수이며, 같으면 0이다. 배달원은 연속한 구역 몇 개를 묶어 한 번에 순회하는데, 이를 구간이라 부른다. 구간은 하나 이상의 연속한 구역으로 이루어지며, 구간에 속한 구역들의 a 값을 모두 더한 값을 그 구간의 순증가량이라 한다. 우체국장은 순증가량이 정확히 K인 구간이 몇 개나 되는지 알고 싶어 한다. 시작 구역 번호나 끝 구역 번호가 하나라도 다르면 서로 다른 구간으로 센다. 예를 들어 a 값이 모두 0이고 K가 0이면, 길이가 1 이상인 모든 구간이 조건을 만족한다. 순증가량이 K인 구간의 개수를 구하는 프로그램을 작성하라. 그러한 구간이 없으면 0을 출력한다.

입력

첫 줄에 구역의 수 N과 목표 순증가량 K가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 60,000, -1,000,000,000 ≤ K ≤ 1,000,000,000) 둘째 줄에 a_1, a_2, ..., a_N이 공백으로 구분되어 주어진다. 각 a_i는 정수이며 -999 ≤ a_i ≤ 999이다.

출력

순증가량이 정확히 K인 구간의 개수를 정수 하나로 출력한다.

5 6
1 2 3 3 0

3

4 0
0 0 0 0

10

3 100
1 2 3

0

출처: Devin.KR 자체 제작