Trinity
Contest: Codeforces Round 983 (Div. 2)
Difficulty rating: 1400
Tags: 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$$$.

Input format:
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$$$.

Output format:
For each test case, output a single integer — the minimum number of operations required.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
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

Example output:
3
1
0
8

Editorial:
Without loss of generality, we assume that every array mentioned below is sorted in non-descending order.
An array $$$b$$$ of $$$k$$$ elements ($$$k \ge 3$$$) will satisfy the problem's criteria iff $$$b_1 + b_2 > b_k$$$. The proof is that $$$b_1 + b_2$$$ is the minimum sum possible of any pair of distinct elements of array $$$b$$$, and if it is larger than the largest element of $$$b$$$, every pair of distinct elements of $$$b$$$ will be larger than any element of $$$b$$$ on its own.
The upper bound for our answer is $$$n - 2$$$. This can be done as follows: we will turn every value from $$$a_2$$$ to $$$a_{n-1}$$$ to $$$a_n$$$ — this way, we only have two types of triangles: $$$(a_1, a_n, a_n)$$$ and $$$(a_n, a_n, a_n)$$$. Since $$$a_1 \ge 1 > 0$$$, we have $$$a_1 + a_n > a_n$$$, which means the former type of triangles is non-degenerate. The latter is also trivially one, as it is a regular/equilateral triangle.
Otherwise, we'll need a pair of indices $$$(i, j)$$$ ($$$1 \le i \le n-2$$$, $$$i+2 \le j \le n$$$), so that in the final array after applying operations to $$$a$$$, $$$a_i$$$ and $$$a_{i+1}$$$ will be respectively the smallest and second smallest element, and $$$a_j$$$ will be the largest element. Such indices must satisfy $$$a_i + a_{i+1} > a_j$$$.
Let's consider a pair $$$(i, j)$$$ that satisfies the above condition, then we need to turn elements outside of it (i.e. those before $$$i$$$ or after $$$j$$$) into some elements within the range $$$[a_{i+1}, a_j]$$$, and indeed we can change them into $$$a_{i+1}$$$ — this way, we have everything in place while keeping the relative rankings of $$$a_i$$$, $$$a_{i+1}$$$ and $$$a_j$$$ as what they are initially. Therefore, for such a pair, the number of operations needed is $$$n - (j - i + 1)$$$. This means that for every $$$i$$$, we need to find the largest $$$j > i$$$ that satisfies the condition, which can easily be done using two pointers.
Sorting complexity: $$$\mathcal{O}(n \log n)$$$.
Two-pointer complexity: $$$\mathcal{O}(n)$$$.