CF2170B Addition on a Segment

你有一个整数数组 $a$，其初始包含 $n$ 个零。你需要执行恰好 $n$ 次如下操作： - 选择两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），并对所有满足 $l \le i \le r$ 的 $i$，执行 $a_{i} = a_{i} + 1$。 现给定另一个长度为 $n$ 的整数数组 $b$，你的任务是为每一次操作选择合适的 $l$ 和 $r$，使得： - 所有 $n$ 次操作执行结束后，可以通过重新排列 $a$ 数组的元素，使 $a$ 变为 $b$； - 在所有操作中，$r - l + 1$ 的最大值尽可能大。 请你求出 $r - l + 1$ 的最大可能值。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$）——表示数组 $b$ 的长度。 每个测试用例的第二行包含 $n$ 个整数 $b_{i}$（$0 \le b_{i} \le n$）——表示数组 $b$ 的各个元素。 输入的额外约束： - 至少存在一种方案可以选择每次操作的 $l$ 和 $r$，并在最后重排元素，将 $a$ 变为 $b$； - 所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示最大的 $r - l + 1$。

以第一个测试用例为例。如果 $n$ 次操作如下： - $l = 3$，$r = 3$ - $l = 1$，$r = 3$ - $l = 3$，$r = 3$ - $l = 3$，$r = 3$ - $l = 3$，$r = 3$ 则数组 $a = [1, 1, 5, 0, 0]$，可重排为 $[0, 5, 1, 0, 1]$。可以看到，此时 $r - l + 1$ 的最大值为 $3$，且这是最优答案。 第二个测试用例： - $l = 1$，$r = 3$ - $l = 2$，$r = 3$ - $l = 3$，$r = 3$ 此时答案为 $3$。 由 ChatGPT 5 翻译