Ecrade 有一个整数数组 $$$a_1, a_2, \ldots, a_n$$$。保证对于每个$$$1 \le i \lt n$$$,$$$a_i \neq a_{i+1}$$$。
Ecrade 可以对数组执行多项操作以使其严格递增。
在每个操作中,他可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并将 $$$a_l, a_{l+1}, \ldots, a_r$$$ 替换为任何 $$$r-l+1$$$ 整数 $$$a'_l, a'_{l+1}, \ldots,a'_r$$$ 满足以下约束:
- 对于每个 $$$l \le i \lt r$$$,$$$a'_i$$$ 和 $$$a'_{i+1}$$$ 之间的比较与 $$$a_i$$$ 和 $$$a_{i+1}$$$ 之间的比较相同,即如果 $$$a_i \lt a_{i + 1}$$$,则$$$a'_i \lt a'_{i + 1}$$$;否则,如果 $$$a_i \gt a_{i + 1}$$$,则 $$$a'_i \gt a'_{i + 1}$$$;否则,如果 $$$a_i = a_{i + 1}$$$,则 $$$a'_i = a'_{i + 1}$$$。
Ecrade 想知道使数组严格递增的最少操作数。不过,好像有点困难,所以请帮助他!
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$)。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)。
保证对于每个 $$$1 \le i \lt n$$$,$$$a_i \neq a_{i+1}$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数,表示使数组严格递增的最小操作数。
示例
输入复制
433 2 133 1 24-2 -5 5 271 9 1 9 8 1 0
输出复制
2 1 1 3
注意
在第一个测试用例中,获得最小操作数的可能方法:
- 在第一个操作中,选择$$$l = 2,r = 2$$$和$$$a'_2 = 4$$$,则$$$a=[3, 4, 1]$$$;
- 在第二个操作中,选择 $$$l = 1、r = 2$$$ 和 $$$a'_1 = -1、a'_2 = 0$$$,然后 $$$a=[-1, 0, 1]$$$。
在第二个测试用例中,获得最小操作数的可能方法:
- 在第一个操作中,选择 $$$l = 2、r = 3$$$ 和 $$$a'_2 = 4、a'_3 = 5$$$,然后 $$$a = [3, 4, 5]$$$。
在第三个测试用例中,获得最小操作数的一种可能方法:
- 在第一个操作中,选择 $$$l = 2、r = 3$$$ 和 $$$a'_2 = -1、a'_3 = 1$$$,然后 $$$a = [-2, -1, 1, 2]$$$。