在马尼拉大都市的摩天大楼林立之中,菲律宾最新的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$$$ 来使柱子的高度不降低。
在第三个测试用例中,柱子的高度已经不减少,因此不需要任何操作。