说明

给定一个升序排列的唯一整数键数组 $x_i$ 和一个非负整数常数 $\varepsilon$。

需要将原始键数组分割成尽可能少的子数组，使得在每个子数组 $[l \ldots r]$ 上，存在某个线性函数 $f(x) = k \cdot x + b$，能够预测该子数组上的键 $x_i$ 的位置（即 $i - l$），且误差不超过 $\varepsilon$。

形式化地，对于第 $j$ 个子数组，必须存在系数 $k_j$ 和 $b_j$（不一定为整数），使得对于该子数组上的所有键 $x_i$（$i \in [l_j \ldots r_j]$），满足：

其中 $f_j(x) = k_j \cdot x + b_j$。

输入格式

输入的第一行包含两个以空格分隔的整数：$n$ 和 $\varepsilon$ —— 分别表示键的数量和最大允许误差（$2 \leq n \leq 10^6$， $0 \leq \varepsilon \leq n$）。

输入的第二行包含以空格分隔的唯一键 $x_i$，按升序排列（$-2\cdot 10^9 \le x_1 < x_2 < \ldots < x_n \le 2\cdot 10^9$）。

输出格式

输出一行一个整数 $m$ —— 为了满足要求，能够将原始键数组分割成的最少子数组数量。

8 0
1 2 3 4 7 10 13 16

2

提示

在示例中，可以将指定的键数组分割成两个子数组：$[1,2,3,4]$ 和 $[7,10,13,16]$。在第一个子数组中，键的位置由函数 $f(x)=x-1$ 精确预测。在第二个子数组中，键的位置由函数 $f(x) = (x-7)/3 = \frac{1}{3}x - \frac{7}{3}$ 精确预测。

翻译由 DeepSeek 完成