题目描述

给定一个数组 $a$ 和一个整数 $X$，你的任务是找出数组 $a$ 中最长的 有效 子序列。一个子序列是 有效 的，当且仅当该子序列中任意相邻元素的乘积都不超过 $X$。也就是说，设 $b$ 是 $a$ 的一个长度为 $m$ 的子序列，则 $b$ 是 有效 的，当且仅当对于任意 $i$ （$1 \leq i \leq m-1$），都有 $b_i \cdot b_{i+1} \leq X$。

注意：数组 $b$ 是另一个数组 $a$ 的子序列，当且仅当 $b$ 可以通过从数组 $a$ 中移除若干元素（也可以不移除）且不改变剩余元素的顺序得到。例如，数组 $[1,3]$ 是 $[1,2,3]$ 的一个子序列，而数组 $[2,1]$ 和数组 $[1,4]$ 不是 $[1,2,3]$ 的子序列。

输入格式

第一行包含两个以空格分隔的整数 $n$ （$1 \leq n \leq 10^5$）和 $X$ （$0 \leq |X| \leq 10^{18}$）—— $n$ 是数组 $a$ 的长度，$X$ 是给定的整数。

第二行包含 $n$ 个以空格分隔的整数 $a_1, a_2, \dots, a_n$ （$1 \leq |a_i| \leq 10^9$）。

输出格式

输出一行一个整数，表示最长 有效 子序列的长度。

1 10
100

1

5 10
3 4 2 5 1

4

5 10
6 -2 -2 -6 5

4

提示

注释

示例 1
只有一个元素的子序列总是有效的，因为不存在相邻元素。因此，最长有效子序列的长度为 $1$。

示例 2
本例中有一个有效子序列 $[3,2,5,1]$。其相邻元素的乘积均不超过 $10$，如下所示：

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

子序列 $[\underline{3,4},2,5,1]$（即原数组 $a$）是 无效 的，因为第一个和第二个元素的乘积为 $12$，超过了 $10$。

因此，最长有效子序列的长度为 $4$。

示例 3
本例中最长有效子序列是 $[6,-2,-2,5]$。

子序列 $[6,-2,\underline{-2, -6}, 5]$（即原数组 $a$）是 无效 的，因为第三个和第四个元素的乘积为 $-2 \times -6 = 12$，超过了 $10$。

计分

子任务 1 （$5$ 分）： $X = 10^{18}$

子任务 2 （$15$ 分）： $n \leq 20$

子任务 3 （$20$ 分）： $n \leq 10^3$

子任务 4 （$10$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $1 \leq a_i \leq 200$

子任务 5 （$20$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $1 \leq a_i \leq 10^5$

子任务 6 （$10$ 分）： $X \geq 0$，且对于所有 $1 \leq i \leq n$，有 $a_i \geq 1$

子任务 7 （$20$ 分）： 无额外限制

翻译由 DeepSeek 完成