CF2032C Trinity

给定 $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 \neq y, y \neq z, z \neq x)$ ，都有以 $a_x, a_y, a_z$ 为长度的三条线段可以构成一个非退化三角形。

**题目有多组数据**。 第一行有一个整数 $T\ (1 \le T \le 10^4)$ ，表示测试数据组数。 对每一组数据， 第一行包括一个整数 $n \ (3 \le n \le 2 \times 10^5)$ 表示数组 $a$ 的元素个数。 第二行有 $n$ 个整数 $a_1, a_2, \ldots, a_n \ (1 \le a_i \le 10^9)$ 表示数组 $a$ 的元素。 保证所有 $n$ 的和不超过 $2 \times 10^5$。

对每一组数据，输出一个整数表示最少操作次数。

对第一组样例，一种可能的操作方式如下： - 令 $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_4 = 4$，数组变为 $[4, 5, 3, 4, 5, 6, 4]$。 可以证明最终的数组符合条件，并且 3 次操作是最少的。 对第二组样例，我们令 $a_1 := a_2 = 3$ 使数组变为 $a = [3, 3, 2]$ 即可。 对第三组样例，既然 $3, 4, 5$ 已经可以构成三角形的三条边，我们并不需要进行任何操作。