CF2170B.Addition on a Segment

You start with an integer array $a$, which initially consists of $n$ zeros. You have to perform the following action exactly $n$ times:

• choose two integers $l$ and $r$ ($1 \le l \le r \le n$) and assign $a_{i} = a_{i} + 1$ for each $i$ such that $l \le i \le r$.

You are given an array $b$, consisting of $n$ integers. Your task is to choose such values $l$ and $r$ for each action that:

• after all $n$ actions are performed, it's possible to reorder the elements in such a way that $a$ becomes equal to $b$;
• the maximum value of $r - l + 1$ over all actions is as large as possible.

What's the maximum possible value of $r - l + 1$?

你从一个整数数组 $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$ 的元素进行重排，使其与 $b$ 完全相等；
• 所有操作中 $r - l + 1$ 的最大值尽可能大。

请问 $r - l + 1$ 的最大可能值是多少？

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^{5}$) — the length of the array $b$.

The second line of each test case contains $n$ integers $b_{i}$ ($0 \le b_{i} \le n$) — the elements of the array $b$.

Additional constraints on the input:

• there exists at least one way to choose $l$ and $r$ for each action and reorder the elements at the end so that $a$ becomes equal to $b$;
• the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^{5}$）—— 数组 $b$ 的长度。

每个测试用例的第二行包含 $n$ 个整数 $b_{i}$（$0 \le b_{i} \le n$）—— 数组 $b$ 的元素。

输入的额外约束条件：

• 对于每个操作，均至少存在一种方式选择 $l$ 和 $r$，并在最后重新排列元素，使得 $a$ 变为 $b$；
• 所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

For each test case, output one integer — the answer to the problem.

对于每个测试用例，输出一个整数——该问题的答案。

Consider the first test case. If the $n$ actions were as follows:

• $l = 3$ and $r = 3$
• $l = 1$ and $r = 3$
• $l = 3$ and $r = 3$
• $l = 3$ and $r = 3$
• $l = 3$ and $r = 3$

The array $a = [1, 1, 5, 0, 0]$, so you can reorder the elements to make it equal to $[0, 5, 1, 0, 1]$. As can be seen in this case, the maximum value of $r - l + 1$ is $3$. It can be shown that this is the optimal answer.

In the second test case:

• $l = 1$ and $r = 3$
• $l = 2$ and $r = 3$
• $l = 3$ and $r = 3$

The answer is $3$.

考虑第一个测试用例。若 $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$。