← 返回题目列表

Codeforces · 2170/B

B. 段上的加法

中文机器翻译题面 查看原题

从一个整数数组 $$$a$$$ 开始,它最初由 $$$n$$$ 零组成。您必须执行以下操作 正是 $$$n$$$ 次:

  • 选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) 并为每个 $$$i$$$ 分配 $$$a_{i} = a_{i} + 1$$$,使得 $$$l \le i \le r$$$。

给定一个数组 $$$b$$$,由 $$$n$$$ 整数组成。您的任务是为每个操作选择这样的值 $$$l$$$ 和 $$$r$$$:

  • 执行完所有 $$$n$$$ 操作后,可以对元素重新排序,使 $$$a$$$ 等于 $$$b$$$;
  • 所有操作的 $$$r - l + 1$$$ 的最大值尽可能大。

$$$r - l + 1$$$ 的最大可能值是多少?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。

输出

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

示例

输入
复制

3
5
0 5 1 0 1
3
3 2 1
5
1 1 1 1 1

输出
复制

3
3
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$$$。