생선

합이 K 이상인 연속 부분 배열의 개수를 센다.

보통7누적 합분할 정복정렬이분 탐색아직 제출이 없습니다시간 제한1초메모리 제한64 MB

문제

고양이 쿠칭은 생선을 좋아한다. 그런데 너무 큰 생선을 사 버려서 전부 먹고 싶지는 않다. 쿠칭은 생선을 머리부터 꼬리까지 NN개의 조각으로 자르고 1번부터 NN번까지 번호를 붙인 다음, 각 조각에 만족도를 매겼다. 만족도가 클수록 그 조각을 먹을 때 더 즐겁다. 생선은 덩어리로 먹어야 맛있다. 한 덩어리는 번호가 연속한 조각 하나 이상으로 이루어진다.

쿠칭은 입맛이 까다로워서 만족도의 합이 KK보다 작은 덩어리는 즐기지 못한다. 즉 합이 KK 이상이어야 한다. 쿠칭이 즐겁게 먹을 수 있는 덩어리 하나를 생선에서 잘라내는 방법이 몇 가지인지 구하라. 덩어리에 들어가지 않은 조각은 버린다.

한 덩어리는 조각을 최소 1개 포함하고, 최대 NN개까지, 즉 생선 전체까지 포함할 수 있다.

입력

첫째 줄에 32비트 부호 있는 정수 NNKK가 주어진다. NN은 항상 양수이고, KK는 양수일 수도 0 이하일 수도 있다. (1N200,0001 \le N \le 200{,}000)

둘째 줄에 조각 NN개의 만족도가 순서대로 주어진다. ii번째 정수는 ii번째 조각의 만족도이다. 만족도는 32비트 부호 있는 정수 범위에 들어가며, 양수일 수도 0 이하일 수도 있다.

출력

쿠칭이 즐겁게 먹을 수 있는 덩어리, 곧 만족도의 합이 KK 이상인 덩어리를 하나 잘라내는 방법의 수를 정수 하나로 출력한다.

힌트

첫 번째 예제에서 쿠칭은 생선을 5조각으로 나누었고 만족도는 차례로 1, -2, 3, -4, 5이며, 합이 2 이상인 덩어리만 즐긴다. 조건을 만족하는 덩어리는 (1, -2, 3), (1, -2, 3, -4, 5), (-2, 3, -4, 5), (3), (3, -4, 5), (5)의 여섯 가지다. 나머지 덩어리는 합이 KK보다 작다. 1번, 3번, 5번 조각은 연속하지 않으므로 (1, 3, 5)는 덩어리가 아니다.