P8049 [COCI 2010/2011 #5] DVONIZ (Enhanced Version)

The statement is the same as the original problem [P7635 [COCI2010-2011#5] DVONIZ](https://www.luogu.com.cn/problem/P7635), except that the Constraints, time and memory limits, and score are different.

We call a sequence of $2\times K$ elements interesting if the sum of the first $K$ elements or the sum of the last $K$ elements is not greater than $S$. Given a sequence $A$ of length $N$, for each position, output the length of the longest interesting subarray starting from that position.

The first line contains integers $N$ and $S$. Each of the next $N$ lines contains one integer $A_i$ from the sequence $A$. All these integers are positive, and their sum does not exceed $2\times 10^9$.

Output $N$ lines in total. The $i$-th line contains an integer representing the length of the longest interesting subarray starting from the $i$-th element. If there is no interesting subarray starting at this position, output `0`.

**Sample Explanation #1** For the first position in Sample $1$, there are $4$ subarrays, and all of them satisfy the condition, so we take the longest one with length $4$. **Constraints** For $30\%$ of the testdata, $2\le N \le 200$. For $50\%$ of the testdata, $2\le N \le 5 \times 10^3$. For $70\%$ of the testdata, $2 \le N \le 2 \times 10^5$. For $100\%$ of the testdata, $2\le N \le 3 \times 10^6$, $1\le S \le 10^9$, $1\le A_i \le 10^9$. Translated by ChatGPT 5