Dvoniz

We say that a sequence of $2K$ elements is interesting if neither the sum of the first $K$ elements, nor the sum of the last $K$ elements, is greater than $S$. A sequence $A$ of length $N$ is given. For every element, output the length of the longest interesting subsequence starting with that element.

The first line contains integers $N$ and $S$ ($2 \leq N \leq 100\, 000$, $1 \leq S \leq 2 \cdot 10^9$ ).

The following $N$ lines contain the sequence $A$, one integer per line. The integers are non-negative and their sum does not exceed $2\cdot 10^9$.

Output $N$ lines. The $i$-th line must contain one integer, the length of the longest interesting subsequence starting with the i-th element. If an interesting subsequence at that position doesn’t exist, output 0 (zero).

Sample Input 1 | Sample Output 1 |
---|---|

5 10000 1 1 1 1 1 |
4 4 2 2 0 |

Sample Input 2 | Sample Output 2 |
---|---|

5 9 1 1 10 1 9 |
2 0 0 2 0 |

Sample Input 3 | Sample Output 3 |
---|---|

8 3 1 1 1 1 1 1 1 1 |
6 6 6 4 4 2 2 0 |