← 返回题目列表

Codeforces · 2032/C

C. 三位一体

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

给定一个数组 $$$a$$$,其中包含 $$$n$$$ 个元素 $$$a_1、a_2、\ldots、a_n$$$。

您可以执行以下操作任意次数(可能是 $$$0$$$):

- 选择两个整数 $$$i$$$ 和 $$$j$$$,其中 $$$1 \le i, j \le n$$$,并分配 $$$a_i := a_j$$$。

求使数组$$$a$$$满足条件所需的最少操作次数:

- 对于每个成对不同的索引三元组 $$$(x, y, z)$$$ ($$$1 \le x, y, z \le n$$$, $$$x \ne y$$$, $$$y \ne z$$$, $$$x \ne z$$$),存在一个边长为 $$$a_x$$$ 的非退化三角形, $$$a_y$$$ 和 $$$a_z$$$,即 $$$a_x + a_y > a_z$$$、$$$a_y + a_z > a_x$$$ 和 $$$a_z + a_x > a_y$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — 数组 $$$a$$$ 中的元素数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 所需的最少操作数。

示例

输入 #1

4
7
1 2 3 4 5 6 7
3
1 3 2
3
4 5 3
15
9 3 8 1 6 5 3 8 2 1 4 2 9 4 7

输出 #1

3
1
0
8

注意

在第一个测试用例中,可能的一系列操作之一是:

- 分配 $$$a_1 := a_4 = 4$$$。该数组将变为 $$$[4, 2, 3, 4, 5, 6, 7]$$$。
- 分配 $$$a_2 := a_5 = 5$$$。该数组将变为 $$$[4, 5, 3, 4, 5, 6, 7]$$$。
- 分配 $$$a_7 := a_1 = 4$$$。该数组将变为 $$$[4, 5, 3, 4, 5, 6, 4]$$$。

可以证明,最终数组中具有成对不同索引的任何三元组元素形成一个非退化三角形,并且使用少于 $$$3$$$ 操作不可能得到答案。

在第二个测试用例中,我们可以分配 $$$a_1 := a_2 = 3$$$ 来创建数组 $$$a = [3, 3, 2]$$$。

在第三个测试用例中,由于 $$$3$$$、$$$4$$$ 和 $$$5$$$ 是三角形的有效边长,因此我们不需要对数组执行任何操作。