Interesting Sequence

Time limit1sMemory limit128 MB

Summary

For each starting index, find the maximum even-length window whose first half sum and second half sum are both at most S, using binary search and prefix sums.

Level: Medium6 of 10
Topics: Binary search, Prefix sum, Two pointers
Solved: No attempts yet

Problem

Consider a sequence of length 2K, where K is a positive integer. If both the sum of the first K elements and the sum of the last K elements are at most S, call the sequence interesting.

Given a sequence A of length N, find, for every starting position, the maximum length of a contiguous subsequence that starts there and is interesting.

Input

The first line contains N and S. (2 <= N <= 100,000, 1 <= S <= 2 * 10^9)

Each of the next N lines contains one element of the sequence A. Every element is positive, and the sum of all elements of A is at most 2 * 10^9.

Output

Print N lines. On the i-th line, print the length of the longest interesting contiguous subsequence that starts at the i-th element. If no such subsequence exists, print 0.

Examples3

Example 1
Input
```
5 10000
1
1
1
1
1
```
Expected output
```
4
4
2
2
0
```
Example 2
Input
```
5 9
1
1
10
1
9
```
Expected output
```
2
0
0
2
0
```
Example 3
Input
```
8 3
1
1
1
1
1
1
1
1
```
Expected output
```
6
6
6
4
4
2
2
0
```