如果 $$$a_1 \leq a_2 \leq \ldots \leq a_{n-1} \leq a_n$$$ 则调用已排序的长度为 $$$n$$$ 的数组 $$$a$$$。
Ntarsis 有一个长度为 $$$n$$$ 的数组 $$$a$$$。
允许他对其执行一种类型的操作(零次或多次):
- 选择索引 $$$i$$$ ($$$1 \leq i \leq n-1$$$)。
- 将 $$$1$$$ 添加到 $$$a_1、a_2、\ldots、a_i$$$。
- 从 $$$a_{i+1}, a_{i+2}, \ldots, a_n$$$ 中减去 $$$1$$$。
操作后$$$a$$$ 的值可以为负数。
确定使 $$$a$$$ 不排序所需的最少操作。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 500$$$) — 数组 $$$a$$$ 的长度。
下一行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 数组 $$$a$$$ 的值。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$500$$$。
输出
输出使数组不排序所需的最少操作数。
示例
输入 #1
4 2 1 1 4 1 8 10 13 3 1 3 2 3 1 9 14
输出 #1
1 2 0 3
注意
第一种情况,我们可以执行 $$$1$$$ 操作来使数组不排序:
- 选择 $$$i = 1$$$。数组 $$$a$$$ 就变成了 $$$[2, 0]$$$,它是未排序的。
对于第二种情况,我们可以执行 $$$2$$$ 操作来使数组不排序:
- 选择 $$$i = 3$$$。数组 $$$a$$$ 则变为 $$$[2, 9, 11, 12]$$$。
- 选择 $$$i = 3$$$。数组 $$$a$$$ 就变成了 $$$[3, 10, 12, 11]$$$,它是未排序的。
可以证明$$$1$$$和$$$2$$$操作分别是第一个和第二个测试用例中的最小操作数。
在第三种情况下,数组尚未排序,因此我们执行 $$$0$$$ 操作。