슬라이드 횟수

프로그래밍 수업에서 슬라이딩 윈도 알고리즘을 사용하여 정수 배열을 분석하는 과제가 주어진다. 구체적으로, $N$개의 정수 $w_1, \ldots, w_N$와 어떤 상수 $C$가 주어질 때, 슬라이딩 윈도 알고리즘은 다음을 만족하도록 시작 인덱스와 끝 인덱스 $s$ 및 $e$를 유지한다.

• 처음에는 $s = e = 1$이다.

• $s \leq N$인 동안 다음을 반복한다.

• $e+1 > N$이면 $s$을 증가시킨다.

• 그렇지 않고 $w_s + \cdots + w_{e+1} > C$이면 다음을 수행한다. $s$를 증가시킨다.

• 그 외에는 $e$을 증가시킨다.

이 알고리즘을 실행하는 동안 서로 다른 각 인덱스 쌍 $(s,e)$은 하나의 윈도를 정의한다. 원소 $w_i$은 $s \leq i \leq e$인 경우 $(s,e)$가 정의하는 윈도에 속한다. $s > e$이면 윈도가 비어 있음에 유의하라.

아래의 첫 번째 예제 입력을 살펴보자. 알고리즘을 실행하는 동안 나타나는 윈도는 $(1,1)$, $(1,2)$, $(1,3)$, $(2,3)$, $(3,3)$, $(3,4)$, $(4,4)$, $(5,4)$, $(5,5)$, 그리고 $(6,5)$에 의해 정의된다.

각 원소 $w_i$에 대해, 슬라이딩 윈도 알고리즘을 실행하는 동안 그 원소가 속하는 서로 다른 윈도의 개수를 구한다.

입력의 첫째 줄에는 두 정수 $N$ ($1 \leq N \leq 100\,000$)과 $C$ ($1 \leq C \leq 1\,000\,000$)가 주어지며, 각각 원소의 개수와 슬라이딩 윈도 상수를 나타낸다.

다음 줄에는 $N$개의 정수 $w_1, \ldots, w_N$ ($0 \leq w_i \leq C$)가 주어진다.

각 원소에 대해, 알고리즘을 실행하는 동안 그 원소가 속하는 서로 다른 윈도의 개수를 순서대로 출력한다.