回想一下,长度 $$$n$$$ 的排列是长度 $$$n$$$ 的序列,使得从 $$$1$$$ 到 $$$n$$$ 的每个整数在其中恰好出现一次。
让我们将排列的成本定义为其需要排序的连续子段(可能为空)的最小长度,以便整个排列按升序排序。
给定一个整数数组 $$$p$$$,由从 $$$0$$$ 到 $$$n$$$ 的整数组成,其中正数(严格大于零)整数不会出现多次。您应该用整数替换零,以便数组 $$$p$$$ 成为排列。
您的任务是计算所得排列的最大可能成本。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \dots, p_n$$$ ($$$0 \le p_i \le n$$$)。在此序列中,正整数不会出现多次。
对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 结果排列的最大可能成本。
示例
输入复制
451 0 4 0 530 0 041 2 3 030 3 2
输出复制
3302
注意
在第一个示例中,您可以使用成本 $$$3$$$ 进行排列 $$$[1, 3, 4, 2, 5]$$$,因为您必须对段 $$$[2, 4]$$$ 进行排序。
在第二个示例中,您可以使用成本 $$$3$$$ 进行排列 $$$[2, 3, 1]$$$,因为您必须对段 $$$[1, 3]$$$ 进行排序。
在第三个示例中,只有一种可能的排列 - $$$[1, 2, 3, 4]$$$,成本为 $$$0$$$,因为排列已经排序。
在第四个示例中,只有一种可能的排列 - $$$[1, 3, 2]$$$,成本为 $$$2$$$,因为您必须对段 $$$[2, 3]$$$ 进行排序。