Description

Given an array $a$ and an integer $X$, you are tasked to find the longest $\textbf{valid}$ subsequence of the array $a$. A subsequence is $\textbf{valid}$ if and only if none of the products of neighbouring elements in the subsequence exceed $X$. That is, suppose $b$ is the subsequence of $a$ with length $m$, $b$ is $\textbf{valid}$ if and only if for any $i$, where $1 \leq i \leq m-1$, $b_i \cdot b_{i+1} \leq X$.

Note: An array $b$ is a subsequence of another array $a$ if $b$ can be created by removing some elements (possibly none) from array $a$ without changing the order of elements. For example, the array $[1,3]$ is a subsequence of $[1,2,3]$, whereas the array $[2,1]$ and the array $[1,4]$ is \textbf{not} a subsequence of $[1,2,3]$.

Input Format

The first line contains two space-seperated integers, $n$ ($1 \leq n \leq 10^5$) and $X$ ($0 \leq |X| \leq 10^{18}$) -- $n$ is the length of array $a$ and $X$ is the integer given.

The second line contains $n$ space-seperated integers, $a_1, a_2, \dots, a_n$ ($1 \leq |a_i| \leq 10^9$).

Output Format

The only line contains an integer, which is the length of the longest $\textbf{valid}$ subsequence.

1 10
100

1

5 10
3 4 2 5 1

4

5 10
6 -2 -2 -6 5

4

Hint

Note

$\underline{Example 1}\\$ A subsequence of one element is always valid because there are no neighbouring elements. Therefore, the length of the longest $\textbf{valid}$ subsequence is $1$.

$\underline{Example 2}\\$ This example has a $\textbf{valid}$ subsequence, $[3,2,5,1]$. It is because the product of the neighbouring elements does not exceed $10$, as shown below.

• $3 \times 2 = 6 \,(\leq 10)$
• $2 \times 5 = 10 \,(\leq 10)$
• $5 \times 1 = 5 \,(\leq 5)$

The subsequence $[\underline{3,4},2,5,1]$ (i.e., the original array $a$) is $\textbf{invalid}$ because the product of the first and second elements is 12, which exceeds $10$.

Therefore, the length of the longest $\textbf{valid}$ subsequence is $4$.

$\underline{Example 3}\\$ The longest $\textbf{valid}$ subsequence is $[6,-2,-2,5]$.

The subsequence $[6,-2,\underline{-2, -6}, 5]$ (i.e., the original array $a$) is $\textbf{invalid}$ because the product of the third and fourth elements is $-2 \times -6 = 12$, which exceeds $10$.

Scoring

Subtask 1 ($5$ points): $X = 10^{18}$

Subtask 2 ($15$ points): $n \leq 20$

Subtask 3 ($20$ points): $n \leq 10^3$

Subtask 4 ($10$ points): $X \geq 0$ and $1 \leq a_i \leq 200$, for all $1 \leq i \leq n$

Subtask 5 ($20$ points): $X \geq 0$ and $1 \leq a_i \leq 10^5$, for all $1 \leq i \leq n$

Subtask 6 ($10$ points): $X \geq 0$ and $a_i \geq 1$, for all $1 \leq i \leq n$

Subtask 7 ($20$ points): No additional constraints