给定一个数组 $$$a$$$,长度为 $$$n$$$,由正整数组成。
您可以对此数组执行以下操作任意次数(可能为零):
- 选择三个整数 $$$l$$$、$$$r$$$ 和 $$$x$$$,使得 $$$1 \le l \le r \le n$$$,并将每个 $$$a_i$$$ 相乘,使得 $$$l \le i \le r$$$ 乘以 $$$x$$$。
请注意,您可以选择任何整数作为 $$$x$$$,它不必是正数。
您必须计算使数组 $$$a$$$ 按严格升序排序的最小操作数(即必须满足条件 $$$a_1 < a_2 < \dots < a_n$$$ )。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组 $$$a$$$。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 — 使 $$$a$$$ 按严格升序排序所需的最少操作数。
示例
输入 #1
3 5 1 1 2 2 2 6 5 4 3 2 5 1 3 1 2 3
输出 #1
3 2 0
注意
在第一个测试用例中,我们可以执行如下操作:
- $$$l = 2$$$, $$$r = 4$$$, $$$x = 3$$$;
- $$$l = 4$$$, $$$r = 4$$$, $$$x = 2$$$;
- $$$l = 5$$$,$$$r = 5$$$,$$$x = 10$$$。
在第二个测试用例中,我们可以执行一个操作,如下所示:
- $$$l = 1$$$, $$$r = 4$$$, $$$x = -2$$$;
- $$$l = 6$$$,$$$r = 6$$$,$$$x = 1337$$$。
在第三个测试用例中,数组 $$$a$$$ 已经排序。