Problem Description

Given a sequence of non-negative integers $ S = {s_1, s_2, ..., s_N} $ of length $ N $ and an integer $ K $. Your task is to find the length of the longest contiguous subsequence of $ S $ that satisfies the following condition:

• The product of all elements in the subsequence is less than or equal to $ K $.

The length of the subsequence must be at least 1. If no such subsequence exists, output $ 0 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ s_1 $ $ s_2 $ : $ s_N $

• The first line contains an integer $N\ (1 \leq N \leq 10^5)$ representing the length of the sequence and an integer $K\ (0 \leq K \leq 10^9)$ separated by a space.
• The next $ N $ lines contain the values of the sequence elements. The $ i $-th line (for $1 \leq i \leq N$) contains $s_i\ (0 \leq s_i \leq 10^9)$.

Output Format

Output the length of the longest contiguous subsequence whose product of all elements is less than or equal to $ K $. If no such subsequence exists, output $ 0 $. Ensure to end the output with a newline.

Sample Input and Output

Sample Input #1

7 6
4
3
1
1
2
10
2

Sample Output #1

4

Sample Input #2

6 10
10
10
10
10
0
10

Sample Output #2

6

Sample Input #3

6 9
10
10
10
10
10
10

Sample Output #3

0

Sample Input #4

4 0
1
2
3
4

Sample Output #4

0

Notes/Hints

Partial Points

This problem has partial scoring. The full score is $ 100 $ points.

• If you solve the dataset where $N \leq 1000$, you will be awarded $ 20 $ points.
• If you solve the dataset without additional constraints, you will be awarded an additional $ 80 $ points on top of the above score.

Sample Explanation 1

Choosing the subsequence $ S[2..5] = s_2, s_3, s_4, s_5 $, the product is $3 \times 1 \times 1 \times 2 = 6$, which is less than or equal to $ K $.

见题面 Input 部分

见题面 Output 部分