题目背景

题面与原题P7635 [COCI2010-2011#5] DVONIZ无异，仅有数据范围，时空限制与分值不同。

题目描述

当前 $K$ 个元素的和或最后 $K$ 个元素的和都不大于 $S$ 时，我们说这个 $2\times K$ 个元素的序列是有趣的。

给出一个长度为 $N$ 的序列 $A$。对于每个元素，输出从该元素开始的最长的有趣的子序列。

输入格式

第一行包含整数 $N$ 和 $S$。

下面的 $N$ 行，每行包含序列 $A$ 中的一个整数 $A_i$。这些整数都是正的且它们的和不超过 $2\times 10^9$。

输出格式

输出共 $N$ 行。第 $i$ 行包含一个整数，表示从第 $i$ 元素开始的最长的有趣的子序列的长度。

如果当前位置上没有有趣的子序列，输出 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 

提示

【样例解释#1】

对于样例 $1$ 的第一个位置，一共有 $4$ 个子序列，且都满足条件，故取最长的长度为 $4$ 的子序列。

【数据范围】

对于 $30\%$ 的数据，$2\le N \le 200$。

对于 $50\%$ 的数据，$2\le N \le 5 \times 10^3$。

对于 $70\%$ 的数据，$2 \le N \le 2 \times 10^5$。

对于 $100\%$ 的数据，$2\le N \le 3 \times 10^6$，$1\le S \le 10^9$，$1\le A_i \le 10^9$。