Books · Interview Problem

Back to problems

Codeforces

Medium

Arrays

Amazon

Books

Find the longest contiguous segment of books whose total reading time does not exceed a given limit.

Acceptance 0%

Start Practice

Problem Statement

You are given an array of positive integers where each value represents the time needed to read one book, in order on a shelf. You have a fixed amount of free time $k$ .

Choose a contiguous sequence of books and read them all. Your task is to determine the maximum number of consecutive books you can read without the total reading time exceeding $k$ .

Input Format

Input

The first line contains two integers $n$ and $k$ .
The second line contains $n$ integers $a_1, a_2, \dots, a_n$ where $a_i$ is the reading time of the $i$ -th book.

Notes

The chosen books must form a contiguous subarray.

Output Format

Output

Print one integer: the maximum length of a contiguous subarray whose sum is at most $k$ .

Constraints

$1 \le n \le 2\cdot 10^5$
$1 \le a_i \le 10^9$
$1 \le k \le 10^{18}$

Examples

Sample cases returned by the problem API.

Example 1

Input

7 8
3 1 2 1 1 1 5

Output

Explanation

The longest valid segment is [1, 2, 1, 1, 1], which has sum 6 and length 5.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress