Slide Count

In your programming class, you are given an assignment to analyze an integer array with a sliding window algorithm. Given $N$ integers $w_1, \ldots, w_N$ and a constant $C$, the algorithm maintains start and end indices $s$ and $e$ as follows.

• Initially $s = e = 1$.
• As long as $s \leq N$:
  • if $e+1 > N$, increment $s$;
  • else if $w_s + \cdots + w_{e+1} > C$, increment $s$;
  • else increment $e$.

Each distinct pair of indices $(s,e)$ that appears during the execution defines a window. Element $w_i$ belongs to the window $(s,e)$ if $s \leq i \leq e$. If $s > e$, the window is empty.

For the first sample, the windows are $(1,1)$, $(1,2)$, $(1,3)$, $(2,3)$, $(3,3)$, $(3,4)$, $(4,4)$, $(5,4)$, $(5,5)$, and $(6,5)$. For each element $w_i$, count how many different windows it belongs to during the execution.

The first line contains two integers $N$ ($1 \leq N \leq 100\,000$), the number of elements, and $C$ ($1 \leq C \leq 1\,000\,000$), the window constant.

The next line contains $N$ integers $w_1, \ldots, w_N$ ($0 \leq w_i \leq C$).

For each element, in input order, print the number of different windows it belongs to during the execution of the algorithm.