← 返回题目列表

Codeforces · 1898/B

B. 米莱娜和仰慕者

中文机器翻译题面 查看原题

Milena 从一位秘密崇拜者那里收到了一个整数数组 $$$a_1, a_2, \ldots, a_n$$$,长度为 $$$n$$$。她认为使其不减少应该有助于她识别秘密崇拜者。

她可以使用以下操作使这个数组不减:

- 选择数组 $$$a$$$ 的一个元素 $$$a_i$$$ 和一个整数 $$$x$$$,使得 $$$1 \le x < a_i$$$。然后,将 $$$a_i$$$ 替换为数组 $$$a$$$ 中的两个元素 $$$x$$$ 和 $$$a_i - x$$$。新元素($$$x$$$ 和 $$$a_i - x$$$)按此顺序放置在数组 $$$a$$$ 中,而不是 $$$a_i$$$ 中。更正式地说,在操作之前让 $$$a_1, a_2, \ldots, a_i, \ldots, a_k$$$ 为数组 $$$a$$$。运算后,等于$$$a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$$$。请注意,每次操作 $$$a$$$ 的长度都会增加 $$$1$$$。

Milena 可以多次执行此操作(可能为零)。她希望您确定她应该执行此操作以使数组 $$$a$$$ 非递减的最少次数。

如果 $$$x_i \le x_{i+1}$$$ 对于所有 $$$1 \le i < k$$$,则长度为 $$$k$$$ 的数组 $$$x_1, x_2, \ldots, x_k$$$ 称为非递减数组。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 不减。

示例

输入 #1

4
3
1 3 2
4
1 2 3 4
3
3 2 1
7
1 4 4 3 5 7 6

输出 #1

1
0
3
9

注意

在第一个测试用例中,Milena 可以用整数 $$$1$$$ 和 $$$2$$$ 替换数组 $$$a$$$ 的第二个元素,因此数组将变为 $$$[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$$$。只需$$$1$$$操作。

在第二个测试用例中,数组 $$$a$$$ 已经是非递减的,所以答案是 $$$0$$$。

在第三个测试用例中,Milena 可以在 $$$3$$$ 操作中使数组 $$$a$$$ 非递减,如下所示。

- 选择 $$$i=1$$$ 和 $$$x=2$$$ 并将 $$$a_1$$$ 替换为 $$$2$$$ 和 $$$1$$$。数组 $$$a$$$ 等于 $$$[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$$$。
- 选择 $$$i=3$$$ 和 $$$x=1$$$ 并将 $$$a_3$$$ 替换为 $$$1$$$ 和 $$$1$$$。数组 $$$a$$$ 等于 $$$[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$$$。
- 选择 $$$i=1$$$ 和 $$$x=1$$$ 并将 $$$a_1$$$ 替换为 $$$2$$$ 和 $$$1$$$。数组 $$$a$$$ 等于 $$$[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$$$。

可以证明,在$$$2$$$或更少的运算中不可能使其不减,所以答案是$$$3$$$。