P15278 [MCO 2025] Subsequence

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]$.

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$).

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

### 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