C. Trinity
binary search; math; sortings; two pointers
You are given an array \(a\) of \(n\) elements \(a_1, a_2, \ldots, a_n\).You can perform the following operation any number (possibly \(0\)) of times: Choose two integers \(i\) and \(j\), where \(1 \le i, j \le n\), and assign \(a_i := a_j\). Find the minimum number of operations required to make the array \(a\) satisfy the condition: For every pairwise distinct triplet of indices \((x, y, z)\) (\(1 \le x, y, z \le n\), \(x \ne y\), \(y \ne z\), \(x \ne z\)), there exists a non-degenerate triangle with side lengths \(a_x\), \(a_y\) and \(a_z\), i.e. \(a_x + a_y > a_z\), \(a_y + a_z > a_x\) and \(a_z + a_x > a_y\).
Each test consists of multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 10^4\)) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer \(n\) (\(3 \le n \le 2 \cdot 10^5\)) — the number of elements in the array \(a\).The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) — the elements of the array \(a\).It is guaranteed that the sum of \(n\) over all test cases does not exceed \(2 \cdot 10^5\).
For each test case, output a single integer — the minimum number of operations required.
In the first test case, one of the possible series of operations would be: Assign \(a_1 := a_4 = 4\). The array will become \([4, 2, 3, 4, 5, 6, 7]\). Assign \(a_2 := a_5 = 5\). The array will become \([4, 5, 3, 4, 5, 6, 7]\). Assign \(a_7 := a_1 = 4\). The array will become \([4, 5, 3, 4, 5, 6, 4]\). It can be proven that any triplet of elements with pairwise distinct indices in the final array forms a non-degenerate triangle, and there is no possible answer using less than \(3\) operations.In the second test case, we can assign \(a_1 := a_2 = 3\) to make the array \(a = [3, 3, 2]\).In the third test case, since \(3\), \(4\) and \(5\) are valid side lengths of a triangle, we don't need to perform any operation to the array.