A16745 | $Addition on a Segment$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

你有一个整数数组 $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$。

输入 #1

输出 #1

3
3
1

C++ 编辑器

输入

输出