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.

Here, a subsequence means a contiguous block of consecutive elements of \(A\).

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

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

Output must consist of \(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).

riseoj 작성

출처 COCI 2010/2011 Contest 5