← 返回题目列表

Codeforces · 2031/A

A. 彭奇克和现代纪念碑

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

在马尼拉大都市的摩天大楼林立之中,菲律宾最新的Noiph购物中心刚刚落成!施工经理彭奇克 (Penchick) 下令用 $$$n$$$ 柱子建造一座最先进的纪念碑。

纪念碑支柱的高度可以表示为 $$$n$$$ 正整数的数组 $$$h$$$,其中 $$$h_i$$$ 表示 $$$1$$$ 和 $$$n$$$ 之间所有 $$$i$$$ 的第 $$$i$$$ 支柱的高度。

Penchick 希望柱子的高度按非递减顺序排列,即 $$$h_i \le h_{i + 1}$$$ 对于 $$$1$$$ 和 $$$n - 1$$$ 之间的所有 $$$i$$$。然而,由于混乱,纪念碑的建造使得柱子的高度按非递增顺序排列,即 $$$h_i \ge h_{i + 1}$$$ 对于 $$$1$$$ 和 $$$n - 1$$$ 之间的所有 $$$i$$$。

幸运的是,Penchick 可以修改纪念碑并根据需要多次对柱子执行以下操作:

- 将柱子的高度修改为任何正整数。形式上,选择一个索引 $$$1\le i\le n$$$ 和一个正整数 $$$x$$$。然后,分配 $$$h_i := x$$$。

帮助 Penchick 确定使纪念碑柱子高度不降低所需的最少操作次数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 50$$$) — 柱子的数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le n$$$ 和 $$$h_i\ge h_{i+1}$$$) — 柱子的高度。

请注意,给定的数组 $$$h$$$ 是非递增的。

请注意,所有测试用例的 $$$n$$$ 总和没有限制。

输出

对于每个测试用例,输出一个整数,表示使柱子高度不减小所需的最小操作数。

示例

输入 #1

3
5
5 4 3 2 1
3
2 2 1
1
1

输出 #1

4
1
0

注意

在第一个测试用例中,柱子的初始高度为 $$$h = [5, 4, 3, 2, 1]$$$。

- 在第一个操作中,Penchick 将柱子 $$$1$$$ 的高度更改为 $$$h_1 := 2$$$。
- 在第二次操作中,他将柱子 $$$2$$$ 的高度更改为 $$$h_2 := 2$$$。
- 在第三次操作中,他将柱子 $$$4$$$ 的高度更改为 $$$h_4 := 4$$$。
- 在第四次操作中,他将柱子 $$$5$$$ 的高度更改为 $$$h_5 := 4$$$。

运算后,柱子的高度为$$$h = [2, 2, 3, 4, 4]$$$,非递减。可以证明,Penchick 不可能在少于 $$$4$$$ 的操作中使柱子的高度不降低。

在第二个测试用例中,Penchick 可以通过将柱子 $$$3$$$ 的高度修改为 $$$h_3 := 2$$$ 来使柱子的高度不降低。

在第三个测试用例中,柱子的高度已经不减少,因此不需要任何操作。