CF1898B Milena and Admirer

Milena 收到了一位神秘仰慕者送来的一个长度为 $n$ 的整数数组 $a_1, a_2, \ldots, a_n$。她认为将这个数组变为非递减序列有助于她识别这位仰慕者。 她可以使用如下操作来使数组变为非递减序列： - 选择数组 $a$ 中的一个元素 $a_i$ 和一个整数 $x$，满足 $1 \le x < a_i$。然后，将 $a_i$ 替换为两个元素 $x$ 和 $a_i - x$，并按顺序将 $x$ 和 $a_i - x$ 插入到原来 $a_i$ 的位置。更正式地说，若操作前数组为 $a_1, a_2, \ldots, a_i, \ldots, a_k$，操作后变为 $a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$。注意，每次操作后数组长度增加 $1$。 Milena 可以进行多次（也可以不进行）这样的操作。她希望你帮她计算，使数组 $a$ 变为非递减序列所需的最少操作次数。 一个长度为 $k$ 的数组 $x_1, x_2, \ldots, x_k$ 被称为非递减的，当且仅当对所有 $1 \le i < k$ 都有 $x_i \le x_{i+1}$。

每个测试包含多组测试用例。第一行包含测试用例个数 $t$（$1 \leq t \leq 10\,000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示数组 $a$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示数组 $a$。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示将数组 $a$ 变为非递减序列所需的最少操作次数。 可以证明，总能在有限次操作内将数组 $a$ 变为非递减序列。

在第一个测试用例中，Milena 可以将数组 $a$ 的第二个元素替换为 $1$ 和 $2$，此时数组变为 $[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$。只需要 $1$ 次操作。 在第二个测试用例中，数组 $a$ 已经是非递减的，所以答案是 $0$。 在第三个测试用例中，Milena 可以通过 $3$ 次操作将数组 $a$ 变为非递减序列，具体如下： - 选择 $i=1$ 和 $x=2$，将 $a_1$ 替换为 $2$ 和 $1$，数组变为 $[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \,]$。 - 选择 $i=3$ 和 $x=1$，将 $a_3$ 替换为 $1$ 和 $1$，数组变为 $[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$。 - 选择 $i=1$ 和 $x=1$，将 $a_1$ 替换为 $1$ 和 $1$，数组变为 $[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$。 可以证明，无法在 $2$ 次或更少操作内使其变为非递减序列，因此答案为 $3$。 由 ChatGPT 4.1 翻译