CF2144B.Maximum Cost Permutation

回忆一下，长度为 $n$ 的排列是一个长度为 $n$ 的序列，使得 $1$ 到 $n$ 的每个整数都恰好出现一次。

我们定义一个排列的代价为：使整个排列递增有序，仅需排序最短的一个连续子段（可以为空）的长度。

现给定一个由 $0$ 到 $n$ 的整数构成的数组 $p$，其中没有任何正整数（大于零）出现超过一次。你需要用整数替换所有的 $0$，使得数组 $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$。

对于每组测试用例，输出一个整数，表示你能构造的排列的最大可能代价。

在第一个样例中，你可以构造排列 $[1, 3, 4, 2, 5]$，其代价为 $3$，因为你需要排序区间 $[2, 4]$。

在第二个样例中，你可以构造排列 $[2, 3, 1]$，其代价为 $3$，因为你需要排序区间 $[1, 3]$。

在第三个样例中，只有唯一的排列 $[1, 2, 3, 4]$，其代价为 $0$，因为排列已经有序。

在第四个样例中，只有唯一的排列 $[1, 3, 2]$，其代价为 $2$，因为你需要排序区间 $[2, 3]$。

由 ChatGPT 5 翻译