Under construction

Still being built. Things may change

Three Slices

Interview

Time limit1sMemory limit1024 MB

Summary
Find the largest M such that the array contains three consecutive blocks of length M, each with sum at most K.
Level

Medium5 of 10

Topics
Binary search, Prefix sum, Sliding window
Solved
No attempts yet

Statement

You are given an array A0,A1,A2,…,AN−1A_{0}, A_{1}, A_{2}, \ldots, A_{N-1} of NN positive integers. You are also given a positive integer KK. Find the largest positive integer MM such that the following condition holds.

  • There exists an integer 0≤i≤N−3M0 \le i \le N-3M such that

    1. ∑j=ii+M−1Aj≤K\sum_{j=i}^{i+M-1}A_{j} \le K
    2. ∑j=i+Mi+2M−1Aj≤K\sum_{j=i+M}^{i+2M-1}A_{j} \le K
    3. ∑j=i+2Mi+3M−1Aj≤K\sum_{j=i+2M}^{i+3M-1}A_{j} \le K

Input

The first line contains two integers NN and KK. The second line contains the NN elements of the array AA in order.

Output

Print the largest positive integer MM that satisfies the condition. If no such MM exists, print 00.

Constraints

  • 1≤N≤5×1051 \le N \le 5 \times 10^{5}
  • 1≤K≤1091 \le K \le 10^{9}
  • 1≤Ai≤1091 \le A_{i} \le 10^{9}

Examples1

  1. Example 1

    Input
    10 10
3 7 4 3 1 3 5 2 5 1
    Expected output
    2