Background

The statement is the same as the original problem P7635 [COCI2010-2011#5] DVONIZ, except that the Constraints, time and memory limits, and score are different.

Problem Description

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.

Input Format

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 Format

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.

5 10000
1
1
1
1
1 

4
4
2
2
0 

5 9
1
1
10
1
9 

2
0
0
2
0 

8 3
1
1
1
1
1
1
1
1 

6
6
6
4
4
2
2
0 

Hint

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